NOIP2007普及组 纪念品分组

第一个方法很容易想到，先将n个数从小到大排序，在后面比较大的数选择一个数+最小的数要=k,当然要满足贪心的要求，足够的接近k，找到了就删除最小的数和这个数，再继续一样的操作，没有找到就可以直接判断结果了，因为剩下的数都是一个数一组的，但是找数可不能直接一个循环查找，n比较大，时间复杂度n^2肯定超时，除非数据不行，所以一般要线性时间或者nlogn才可以，所以使用二分查找logn时间复杂度，但是还要删除数啊，普通数组删除数比较麻烦，所以使用STL的vector，比较方便。

赋代码：

#includecstdio
#includecstring
#includealgorithm
#includevector
using namespace std;
vectorintG;
int n,k;
void match(int Min)
{
	int r=0;
	int l=G.size()-1;
	while(rl)
	{
		int tmp=(r+l)1;
		if(G[tmp]Min)
		{
		   if(l!=tmp)
		   l=tmp;	
		   else
		   break;
		}
		else
		{
			if(r!=tmp)
			r=tmp;
			else
			break;
		}
	}
	if(rl) 
	for(int i=l;i=r;i--)
	{
		if(Min=G[i])
		{
     	   G.erase(G.begin()+i);
     	   return ;
        }
    }
    else
    {
    	G.erase(G.begin()+r);
	}
} 
int main()
{
	scanf("%d%d",k,n);
	for(int i=0;in;i++)
	{
		int m;
		scanf("%d",m);
		G.insert(G.begin()+G.size(),m);
	}
	sort(G.begin(),G.end());
	int cnt=0;
	bool isok=true;
	while(isok)
	{
		int Min = *G.begin();
		G.erase(G.begin());
		if(G.size()==0)
		{
			cnt++;
		    break;
	    }
		if(Min + *G.begin()k)
		{
			cnt++;
			cnt+=G.size();
		    break;
	    }
	    match(k-Min);
		cnt++;
	}
	printf("%d\n",cnt);
	return 0;
}

第二个方法，首先以为都是一个数一组，组数=n，再判断最大的数是否可以和最小的的数一个组，不可以就说明，最大的数肯定是单独一个组的，删除最大的数，组数不变，如果可以就删除最大的数和最小的数，组数-1，因为最大的数的组可以删除了。

#includecstdio
#includealgorithm
using namespace std;
int n,k;
int ans[31000];
int main()
{
  scanf("%d%d",k,n);
  for(int i=0;in;i++)
    scanf("%d",ans[i]);
  sort(ans,ans+n);
  int cnt=n,r=0,l=n-1;
  while(rl)
  {
      if(ans[r]+ans[l]=k)
      {
          cnt--;
          r++;
          l--;
      }
      else l--;
  }
  printf("%d",cnt);
  return 0;
}