洛谷题单指南-贪心-P1094 [NOIP2007 普及组] 纪念品分组

原题链接：https://www.luogu.com.cn/problem/P1094

题意解读：贪心选择

解题思路：

贪心策略：

将纪念品按价格由小到大排序，优先选择价格大的一直到超过分组价格上限，再选择价格小的直到超过价格上限，此为一组

重复以上过程，直到所有数据都遍历到，采用一头一尾双指针即可。

证明：如果最大价格不是和最小价格分在一组，则一定可以被最小价格替代，且有可能放入更多的纪念品，所以最大价格一定要和最小价格放在一起，或者最大价格单独一组。

100分代码：

#include <bits/stdc++.h>
using namespace std;

const int N = 30005;

int a[N], w, n, ans;

int main()
{
    cin >> w >> n;
    for(int i = 1; i <= n; i++) cin >> a[i];
    sort(a + 1, a + n + 1);

    int i = 1, j = n;
    int group = 0;
    while(i <= j)
    {
        while(group + a[j] <= w) group += a[j--]; //选择价格大的直到超过分组限制
        while(group + a[i] <= w) group += a[i++]; //选择价格小的直到超过分组限制
        
        ans++;
        group = 0;
    }

    cout << ans;

    return 0;
}