线上OJ:
一本通:1939:【07NOIP普及组】纪念品分组 (opens in a new tab)
AcWing:430. 纪念品分组 (opens in a new tab)
洛谷:P1094 [NOIP2007 普及组] 纪念品分组 (opens in a new tab)
核心思想:
核心语句是“每组最多只能包括两件纪念品”
,所以本题不需要使用背包,可以直接贪心。
题解代码:
#include <bits/stdc++.h>
using namespace std;
const int N = 30005;
int w, n, p[N], ans;
int main()
{
scanf("%d %d", &w, &n);
for(int i = 1; i <= n; i++) scanf("%d", &p[i]);
sort(p + 1, p + 1 + n); // 默认升序排序
for(int i = n, j = 1; i >= j; i--) // 每次末尾最大的数都取,i每次都前移
{
ans++;
if(p[i] + p[j] <= w) j++; // 如果队首最小的数加进去不超过 w ,则队首加进去,指针后移
}
printf("%d", ans);
return 0;
}