【题目描述】
学生节到了，校领导决定由马导曹导许导大导中导小导等全体辅导员为广大学生群众准备纪念品。李华奉命负责新年晚会的纪念品发放工作。为使得参加晚会的同学所获得的纪念品价值相对均衡，他要把购来的纪念品根据价格进行分组，但每组最多只能包括两件纪念品，并且每组纪念品的价格之和不能超过一个给定的整数。为了保证在尽量短的时间内发完所有纪念品，李华希望分组的数目最少。

你的任务是写一个程序，找出所有分组方案中分组数最少的一种，输出最少的分组数目。

【输入】
输入包含 T 组数据。
第 1 行包含一个整数 T，表示数据组数。

在每一组数据中：
第 1 行包括一个整数 w，为每组纪念品价格之和的上限。
第 2 行为一个整数 n，表示购来的纪念品的总件数。
第 3 \sim n+2 行每行包含一个正整数 p_i（5 \le p_i \le w），表示所对应纪念品的价格。

【输出】
每组数据输出一行，包含一个整数，即最少的分组数目。T 组数据，共输出 T 行。

【输入输出样例】
输入

<code>1//包含1组数据
100//每组纪念品的价格之和上限为100
9//购买的纪念品的总件数
90//纪念品1的价格
20
20
30
50
60
70
80
90//纪念品9的价格</code>

输出

<code>6</code>

【限制】
70% 的数据满足：1\le T\le5
50% 的数据满足：1 \le n \le 15
100% 的数据满足：1 \le n \le 30000,\ 80 \le w \le 200,\ 1\le T\le30

简化要求:

根据价格分组，每组价格中奖品的价格之后不超过给定整数，并且每组奖品最多两件且实现分组最少，输出最少的分组数目

思路：

本题使用了贪心算法，贪心表现在分组过程中尽可能让每一组都有两个奖品在其中

首先我先设置一个纪念品数组来记录纪念品的价格，然后我对纪念品价格进行从大到小进行排序，然后把最大的和最小的进行相加，如果最大加最小超过了给定最高价格w,那么最大的那个奖品只能单独分组了，如果最大的和最小的进行相加的价格不超过给定的最高价格w，那么最大和最小成组，随后进行下一轮判断，这里如何自动进行下一轮判断呢，我的做法是令一个变量a和一个变量b,a代表左值/左指针（顾名思义是数轴左边的值），b代表右值/右指针，这里隐含着循环结束的标志，那就是当左值大于右值的时候结束（同样的循环持续进行的标志是a<=b）,一开始令a = 0（代表着最大值），b=n-1(代表着最小值)，然后进入if语句判断和是否大于w,如果大于w,那么标记为单独成组，b不动,a++进入下一轮对比，同样的如果小于w，那么标记为联合成组,a和b同时++，进入下一轮，判断搞定了，那如何标记呢，我的做法是设立一个标记数组cnt,如果a值单独成组的话，那么cnt[a]就为1，如果a,b是联合成组的话，那么cnt[a]=cnt[b]=0，这样一来我们只需要在最后遍历cnt数组，找出cnt_1和cnt_0的个数，那么答案就是cnt_1+cnt_0/2了，至此整个算法逻辑自洽，下面是代码演示：

<code>#include <stdio.h>
#include <stdlib.h>
int list[30000] = {0};//用来存放每个纪念品的价格
int cnt[30000] = {0};//计数器
int cmp(const void *a, const void *b)
{
    int x = *(int *)a;
    int y = *(int *)b;
    if (x > y) return -1;
    if (x < y) return 1;
    return 0;
}
int main(void)
{
	int t,x,z;
	scanf("%d",&t);
	for(x=0;x<t;x++)
	{
		for(z=0;z<30000;z++)
		{
			list[z] = 0;
			cnt[z] = 0;
		} //计数器和存储器归零 
		int w,n,y,a,b;//w为每组上限，n为每组数量，a,b为左值和右值 
		scanf("%d",&w);
		scanf("%d",&n);
		for(y=0;y<n;y++)
		{
			scanf("%d",&list[y]);
		}
		qsort(list,n,sizeof(int),cmp);//从大到小排序
		a = 0;
		b = n-1;
		while(a<=b)
		{
			if(a==b)
			{
				cnt[a] = 1;
				a++;
			 } 
			else if(list[a]+list[b]>w)
			{
				cnt[a] = 1;
				a++;
			}
			else
			{
				cnt[a] = cnt[b] = 0;
				a++;
				b--;
			}
		}
		int cnt_0=0,cnt_1=0,ans;/*cnt_0用来记录为零的值个数，
		cnt_1用来记录为1的值的个数*/ 
		for(y=0;y<n;y++)
		{
			if(cnt[y] == 0) cnt_0++;
			else cnt_1++; 
		}
		
		ans = cnt_1+cnt_0/2;
		printf("%d\n",ans);
	}
	return 0;
}</code>

这里值得注意的是:

1.对于万以上数据的数组优先放在函数外部当全局数组，防止栈溢出

2.if 分支不加 else if，导致连续执行、下标越界

3.while循环要注意考虑到a=b的情况，如果a=b了，那么只能单独分组，即单独开一个if来判断，如果a=b,则cnt[a]=1

4.数组只有在初始化时才能赋初值为0，如int list[10000]={0};

双指针 = 两个标记位置的下标，从两头往中间走，配合判断，一遍循环做完事情，时间复杂度 O(n)。本题属于对撞双指针（一头一尾，相向而行）