纪念品分组

题意：

对一堆价值为tr[i]的纪念品进行分组，每组最多两件，且每组的价值不能超过w，输出最少的分组数目

思路：

是个贪心，需要找到最少的数目，就得尽量让小的去找大的，还得是总和不超过w

我们可以取两个变量l和r，一个在数组头一个在数组尾，开始找，如果说tr[l] + tr[r]的值小于等于w，就说明找到一组，如果大于w了，就让右指针r左移一位，更新答案，然后继续找。

#include <cstdio>
#include <cstring>
#include <string>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#include <stdlib.h>
#include <sstream>
#include <map>
#include <set>
using  namespace std;
#define inf 0x3f3f3f3f
#define MAX 10000000 + 7
#define endl '\n'
#define mod 1e9+7;
typedef  long long ll ;
//不开longlong见祖宗！
inline __int128 read(){__int128 x = 0, f = 1;char ch = getchar();while(ch < '0' || ch > '9'){
    if(ch == '-'){f = -1;}ch = getchar();}while(ch >= '0' && ch <= '9'){
        x = x * 10 + ch - '0';ch = getchar();}return x * f;}
inline void print(__int128 x){if(x < 0){putchar('-');x = -x;}if(x > 9){print(x / 10);}putchar(x % 10 + '0');}

int w,n;
int tr[MAX], sum = 0, ar[MAX];
int main(){
    cin>>w>>n;
    for(int i = 1; i <= n; ++i){
        cin>>tr[i];
    }
    sort(tr + 1, tr + 1 + n);
    int l = 1, r = n;
    while (l < r) {
        if(tr[l] + tr[r] <= w){
            sum++;
            l++;r--;
        }
        else{
            sum++;
            r--;
        }
    }
    if(l == r)sum++;//特判，如果最终l = r说明这个位置的值并没有算进答案里
    cout<<sum<<endl;
    return 0;
}