题目

题目描述：
元旦快到了，校学生会让乐乐负责新年晚会的纪念品发放工作。
为使得参加晚会的同学所获得 的纪念品价值相对均衡，他要把购来的纪念品根据价格进行分组。
但每组最多只能包括两件纪念品， 并且每组纪念品的价格之和不能超过一个给定的整数。
为了保证在尽量短的时间内发完所有纪念品，乐乐希望分组的数目最少。
你的任务是写一个程序，找出所有分组方案中分组数最少的一种，输出最少的分组数目。

输入描述：
第 1 行包括一个整数 w，为每组纪念品价格之和的上限。
第 2 行为一个整数n，表示购来的纪念品的总件数。
第 3 ~ n+2 行每行包含一个正整数 pi ( 5 ≤ pi ≤ w ) ，表示所对应纪念品的价格。

输出描述：
包含一个整数，即最少的分组数目。

解析

根据题目意思，为什么要讲题目，没错我又看错题了。题目要求每组最多两个纪念品，要使组数尽量少（这么瞎，我选拔赛怎么办啊orz）。
  • 既然要组数尽量少，非常容易的就会想到：每组的纪念品价格要尽量的大。

算法讲解：
  1. 我们要价格大，题目给了我们一个非常方便的条件：所有物品价格都没有要求价格大（虽然有也没事，这些买不了）。
  2. 那我们怎么分组呢？这道题毫无疑问就是贪心，而且贪的就是每个价格最大。
  3. 所以我们理所当然的就想到了：组里面放一个最大的，然后与之相配，就看能不能加一个最小的就可以了
    （为什么一定是最小的呢？因为你最大的不用，给别的用也一样，别的要是只能用最小的，给他也没有意义，不如不给）。
  4. 所以我们取左右端点，判断当前最大最小是不是可以组队，不能组就缩右边，能就两边一起缩。

打代码哈：
  1. 我们先保存价值的数组。
  2. 然后排个升序。
  3. 然后左右区间进行操作就行了。
  4. 看代码哈~

AC代码 

#include <iostream> 
#include <algorithm>
using namespace std; 
#define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); 
//代码预处理区 

const int INF = 0x3f3f3f3f;
const int MAX = 3e4 + 7; 
int w, n, val[MAX];
//全局变量区 

int main() { 
    IOS;
    cin >> w >> n;
    for (int i = 1; i <= n; i++) cin >> val[i];
    sort(val + 1, val + 1 + n);
    int l = 1, r = n, cnt = 0;
    while (l < r) {
        if (val[l] + val[r] <= w) l++;//这一对可以用，小的就也用上了
        r--;
        cnt++;
    }
    if (l == r) cnt++;
    cout << cnt << endl;
    return 0; 
}
//函数区