[NOIP 2007 普及组] 纪念品分组

知识点

排序、贪心、双指针

解题思路

将价格排序，从最贵纪念品开始处理。若它与最便宜的未处理纪念品之和不超过上限，就将二者同组；否则最贵的只能单独一组。两种情况都消去最贵元素并累计组数。

正确性说明

若最便宜也无法与最贵配对，任何其余元素都更贵，因此最贵必须独组。若可以配对，可将任意最优方案中的最贵改与最便宜配对：把原来对应的其余元素配在一起仍不超过原较贵搭配的和，或腾出一个空位，不增加组数。故每步贪心可扩展为最优方案。

易错点

每组最多两件；恰好等于上限可以配对；最后只有一件时只计一组，不能与自身配对。

复杂度

排序时间O(n log n)，双指针O(n)，保存数组O(n)。

参考代码（GNU C++17）

#include<bits/stdc++.h>
using namespace std;
int main(){
    int w,n;cin>>w>>n;vector<int>a(n);for(int &x:a)cin>>x;sort(a.begin(),a.end());
    int l=0,r=n-1,ans=0;while(l<=r){if(l<r&&a[l]+a[r]<=w)++l;--r;++ans;}
    cout<<ans<<'\n';
}