纪念品分组|贪心

废话少说，上代码

#include<iostream>
#include<algorithm>
using namespace std;
int main(){
    // 取消iostream和stdio的同步，提高输入输出效率
    ios::sync_with_stdio(false);
    // 解除cin与cout的绑定，进一步优化输入输出 
    cin.tie(nullptr);
    cout.tie(nullptr);
    // w: 价格限制, n: 纪念品数量, p[]: 存储纪念品价格的数组, cnt: 记录分组的数量, left: 左指针
    int w=0,n=0,p[30001]={0},cnt=0,left=0;
    // 输入价格限制和纪念品数量 
    cin>>w>>n;
    // 输入每个纪念品的价格
    for(int i=0;i<n;++i)
        cin>>p[i];
    // 对纪念品价格进行升序排序
    sort(p,p+n);
    // 使用双指针法计算最少分多少个组
    // right从最大价格开始，left从最小价格开始 
    for(int right=n-1;right>=left;--right){
        // 如果最便宜的物品和当前最贵的物品可以同组（价格之和不超过限制）
        if(p[left]+p[right]<=w) 
            left++; // 则将最便宜的纪念品配对上组，左指针右移 
        cnt++; // 每次循环都需要一个组来运走当前最贵的纪念品
    }
    // 输出所需的最少组数
    cout<<cnt;
    return 0;
}