贪心题

是这样的：我们要向让分的组数最少，肯定是希望尽可能多地进行纪念品配对。

那么如何配对就成为了需要思考的问题。

如果想要通过$3e4$的数据，就需要运用贪心：

1.如果一个纪念品和最便宜的纪念品都不能配对，是不是说明它只能自己走？

2.之后是不是说明，还有第二贵、第三贵等等在等着？我们可以去找一个贵的纪念品和便宜的纪念品配对。

3.所以，是不是需要再将剩下的纪念品去和最便宜的配对，这样才能收益最大化？

所以梳理一下：我们找到了一个最便宜的纪念品，之后去后边寻找没配对的、最贵重的纪念品，看看能不能配对。如果不能配对，就说明这个最贵的纪念品不可能和任何纪念品配对了，所以只能自己一组了。如果能配对，介于上述过程，不会有比现在找到的最贵的纪念品还贵的纪念品，所以此二者配对是最优解。

配对完成之后，我们还需要继续寻找下一个便宜的纪念品，继续重复上述过程。

这里需要使用sort函数进行排序，目的是便于按顺序寻找最贵最便宜的纪念品。

代码如下：

#include<iostream>
#include<algorithm>
using namespace std;
const int N=3e4+10;
int a[N];//存储的是纪念品的价值
int main(){
    int M,n;//此处M代指题目中给出的价格之和的上限
    cin>>M>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    sort(a+1,a+n+1);
    int i=1,j=n;//分别对应最便宜的、最贵的纪念品
    int ans=0;
    while(i<=j){
        if(a[i]+a[j]<=M) i++;//对应我们说的，如果可以配对，那么是最优解，我们可以去寻找下一个便宜的纪念品了
        j--;//如果配对了，当下最贵的不用配对，移出去；如果没配对，当下最贵的只能自己走，还是得移出去
        ans++;//两种：一是没配对，i不动，j走了，计入一种分组；二是配对成功，i、j都移动了，还是计入一次分组
    }
    cout<<ans;
    return 0;
}