题目描述

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

输入描述:

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

输出描述:

包含一个整数，即最少的分组数目。

示例1

输入
100
9
90
20
20
30
50
60
70
80
90
输出
6

备注:

50%的数据满足：
100%的数据满足：

解答

把纪念品的价格按照从低到高排列，然后用两个指针(其实是两个 int 型的变量，用来表示下标)，每次选择当前价格最高与价格最低的最为一组，若符号条件，则左边的指针向右移动 1，右边的指针向左移动 1；如果不行就让价格最高的单独分一组，而价格最低再和价格次高作为一组进行判断。
这样贪心下来就能使分的组数最少。
例如价格最低的是 Min，价格最高的是 Max，若 Max + Min 是大于给定的数 w，则说明不能分成一组，若这个时候 Max 再去加其他的价格，只会使得结果更大，则肯定大于 w，所以就不能分成一组。所以这个时候 Max 要自己分一组。
具体步骤：
1.定义数组，用来存储纪念品的价格：
	const int N = 3e4 + 10;
	int a[N];  // 用来存储纪念品的价格
2.定义 2 个变量 w 和 n，并输入 w 和 n： 
int w;  // 每组纪念品价格之和的上限
	int n;  // 纪念品的个数 
	cin >> w >> n;
3.输入 n 个纪念品的价格： 
for (int i = 1; i <= n; i++) {  // 输入 n 个纪念品的价格 
		cin >> a[i];
	}
4.用 sort 给数组 a (纪念品的价格)升序排序： 
sort(a + 1, a + n + 1);  // 将纪念品的价格升序排序(按照价格从低到高进行排列) 
5.定义 3 个变量： 
int l = 1;  // 左边的指针(其实是表示下标的)      int r = n;  // 右边的指针(其实是表示下标的)     int cnt = 0;  // 计数器，用来记录组数 
6.当左边的指针小于等于右边的指针时，做以下操作：
（1）若两个指针指向的纪念品价格能组成一组，则左边的指针向右移动 1，右边的指针向左移动 1，组数加 1。 
if (a[l] + a[r] <= w) {  // 若两者之和小于等于 w，可以分成一组 
		l++;  // 左边的指针(下标)加 1 
		r--;  // 右边的指针(下标)减 1
		cnt++;  // 计数器加 1，a[l] 和 a[r] 作为一组，组数加 1 
	}
（2）若两个指针指向的纪念品价格不能组成一组，右边的指针指向的纪念品自己是一组，组数加 1，且将右边的指针向左移动 1 (左边的指针不动，等待下一次分组)。 
else {  // 若不能分成一组 
		r--;  // // 右边的指针(下标)减 1 (左边的指针不变)
		cnt++;   // 计数器加 1，a[r] 自己作为一组 
	}
7.输出结果： 
cout << cnt;  // 输出计数器，即为最少的组数  

思考：

1.如何证明这样的贪心方案能得到最优解呢？
2.这里的指针是指什么？怎样使用这样的指针？你会使用了麽？

完整代码： 

#include <bits/stdc++.h>

using namespace std;

const int N = 3e4 + 10;
int a[N];  // 用来存储纪念品的价格 

int main() {
	
	int w;  // 每组纪念品价格之和的上限。
	int n;  // 纪念品的个数 
	cin >> w >> n;
	for (int i = 1; i <= n; i++) {  // 输入 n 个纪念品的价格 
		cin >> a[i];
	}
	sort(a + 1, a + n + 1);  // 将纪念品的价格升序排序(按照价格从低到高进行排列) 
	int l = 1;  // 左边的指针(其实是表示下标的) 
	int r = n;  // 右边的指针(其实是表示下标的)
	int cnt = 0;  // 计数器，用来记录组数 
	while (l <= r) {  // 当左边的指针小于等于右边的指针时，记得要有等号 
		if (a[l] + a[r] <= w) {  // 若两者之和小于等于 w，可以分成一组 
			l++;  // 左边的指针(下标)加 1 
			r--;  // 右边的指针(下标)减 1
			cnt++;  // 计数器加 1，a[l] 和 a[r] 作为一组，组数加 1 
		} else {  // 若不能分成一组 
			r--;  // // 右边的指针(下标)减 1 (左边的指针不变)
			cnt++;   // 计数器加 1，a[r] 自己作为一组 
		}
	}
	cout << cnt;  // 输出计数器，即为最少的组数 

	return 0;
}


来源：小韦同学