题解 P1094 【纪念品分组】

2018-03-23 16:32:21


这里我的方法是将纪念品集合看做一个 std::deque<int>,首先将其排序。然后在保证集合非空的情况下,每次判断首元素和尾元素相加是否 $\leq w$ 且集合元素数量大于 $2$ ,如果是就把首尾 $2$ 个元素看做一组,将其剔除集合,并将计数器 $+1$ ,否则尾元素单独一组,将计数器 $+1$ 后将其剔除集合。

#include <cstdio>
#include <deque>
#include <algorithm>

const int MAX_N = 3e4;

int main() {
    int w;
    scanf("%d", &w);

    int n;
    scanf("%d", &n);

    std::deque<int> P;
    for (int i = 1; i <= n; ++i) { int x; scanf("%d", &x); P.push_back(x); }

    std::sort(P.begin(), P.end());

    int ans = 0;
    while (!P.empty()) {
        if (P.size() >= 2 && P.front() + P.back() <= w) {
            P.pop_front();
            P.pop_back();
            ++ans;
        } else {
            P.pop_back();
            ++ans;
        }
    }

    printf("%d\n", ans);

    return 0;
}