题解 P1094 【纪念品分组】
STLGirlfriend
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;
}
```