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;
}
最新回复(0)
/jishuVfqFtSi82c5PQXjvtBW5M6Rcs_2Ba2Z_2BIDWutGaQ_3D_3D4795416
8 简首页