pku 3399 贪心,考虑多种情况.txt

ACM资料大集合

#include <stdio.h>
#include <iostream>
#include <stdlib.h>
#include <vector>
#include <math.h>
#include <algorithm>
#include <iterator>
using namespace std;

//PKU 3399 贪心,考虑多种情况
#define NMAX 105
#define INFI 99999
#define MH make_heap
#define OH pop_heap
#define PH push_heap
#define PB push_back
#define OB pop_back

int ti[NMAX];
int ans[NMAX];
bool cmp_abs(int a,int b)
{
	return abs(a)>abs(b);
}

bool cmp(int a,int b)
{
	return a>b;
}
void solve(int num,int knum)
{
	int i,j,fnum=0,max,min,minnum,maxnum,mmax,mmin,mmaxnum,mminnum,znum;
	sort(ti+1,ti+1+num,cmp_abs);
	for(i=1;i<=knum;i++)
		if(ti[i]<0) fnum++;//已有集合的负数的个数
	
	if(fnum%2==0) 
	{
		for(i=1;i<=knum;i++) ans[i]=ti[i];
		sort(ans+1,ans+1+knum,cmp);
	}	
	else
	{
		max=-1;
		min=1;
		for(i=knum+1;i<=num;i++)
		{
			if(ti[i]>0 && ti[i]>max) {max=ti[i];maxnum=i;}//另一集合的最大正数maxnum
			if(ti[i]<0 && ti[i]<min) {min=ti[i];minnum=i;}//另一集合的最小负数minnum
		}
		mmin=-30005;
		mmax=30005;
		for(i=1;i<=knum;i++)
		{
			if(ti[i]<0 && ti[i]>mmin) {mmin=ti[i];mminnum=i;}//已有集合的最大负数mminum 
			if(ti[i]>0 && ti[i]<mmax) {mmax=ti[i];mmaxnum=i;}//已有集合的最小正数mmaxnum
		}
		if(knum==fnum)//已有集合没有正数
		{
			if(max!=-1)//另一集合有正数，去掉一个最大负数,加入ti[maxnum]（这个负数一定存在）
			{
				for(i=1,j=0;i<=knum;i++) 
				{
					if(i!=mminnum) ans[++j]=ti[i];//把ti[mminnum]剔出
				}
				ans[++j]=ti[maxnum];//加入ti[maxnum]
				sort(ans+1,ans+1+knum,cmp);
			}
			else//另一集合没有正数，也就是说整个序列都是非正数
			{
				znum=0;
				for(i=1;i<=num;i++) if(ti[i]==0) znum++;
				if(znum==0)
				{//都是负数
					sort(ti+1,ti+1+num,cmp);
					for(i=1;i<=knum;i++) ans[i]=ti[i];
				}
				else
				{	//序列中的零只在这里有用
					for(i=1;i<=knum-1;i++) ans[i]=ti[i];
					ans[i]=0;
					sort(ans+1,ans+1+knum,cmp);
				}
			}
		}
		else//已有集合有正数，此时有2种情况：
		//（1）如果另一集合有正数，则剔出最大负数，加入ti[maxnum]，或（2）的做法，二者取最好的选择
		//（2）如果另一集合没有正数，则剔出已有集合的最小正数，加入另一集合的最小负数
		{
			if(max!=-1)
			{
				if(max*mmax>mmin*min) // max/mmin>min/mmax
				{//（1）
					for(i=1,j=0;i<=knum;i++) 
					{
						if(i!=mminnum) ans[++j]=ti[i];//把ti[mminnum]剔出
					}
					ans[++j]=ti[maxnum];//加入ti[maxnum]
					sort(ans+1,ans+1+knum,cmp);
				}
				else
				{//（2）
					for(i=1,j=0;i<=knum;i++) 
						if(i!=mmaxnum) ans[++j]=ti[i];
					ans[++j]=ti[minnum];
					sort(ans+1,ans+1+knum,cmp);
				}
			}
			else
			{
				for(i=1,j=0;i<=knum;i++) 
					if(i!=mmaxnum) ans[++j]=ti[i];
				ans[++j]=ti[minnum];
				sort(ans+1,ans+1+knum,cmp);
			}
		}
	}
	for(i=1;i<=knum;i++) printf("%d ",ans[i]);
	printf("\n");
}
int main()
{	int i,num,knum;
	while(scanf("%d %d\n",&num,&knum)!=EOF)
	{
		for(i=1;i<=num;i++) scanf("%d",&ti[i]);
		solve(num,knum);
	}
	return 0;
}