首页 > 代码库 > poj 3399 Product(模拟)

poj 3399 Product(模拟)

# include <stdio.h>
# include <string.h>
# include <algorithm>
using namespace std;
int cmp(int x,int y)
{
	return x>y;
}
int main()
{
	int a[110],a1[110],a2[110],ans[110];
	int n,k,k1,k2,i,k3;
	while(~scanf("%d%d",&n,&k))
	{
		k1=0;
		k2=0;
		for(i=0;i<n;i++)
		{
			scanf("%d",&a[i]);
			if(a[i]>0)//存正数
				a1[k1++]=a[i];
			else//存负数
				a2[k2++]=a[i];
		}
		sort(a1,a1+k1);
		sort(a2,a2+k2,cmp);//负数从大到小
		k3=0;
		if(k%2)//k为奇数
		{
			k--;
			if(k1>0)
			{
				ans[k3++]=a1[--k1];//先选一个最大的正数
			}
			else//全部为负数的情况
			{
				for(i=0;i<=k;i++)//因为为奇数,选大的负数
				{
					if(i==0)
						printf("%d",a2[i]);
					else
						printf(" %d",a2[i]);
				}
				printf("\n");
				continue;
			}
		}
		for(i=0;i<k/2;i++)//剩下k/2对
		{
			if(k1>=2&&k2>=2)
			{
				int t1=a1[k1-1]*a1[k1-2];
				int t2=a2[k2-1]*a2[k2-2];
				if(t1>t2)//选大的
				{
					ans[k3++]=a1[--k1];
					ans[k3++]=a1[--k1];
				}
				else
				{
					ans[k3++]=a2[--k2];
					ans[k3++]=a2[--k2];
				}
			}
			else if(k1>=2)
			{
				ans[k3++]=a1[--k1];
				ans[k3++]=a1[--k1];
			}
			else if(k2>=2)
			{
				ans[k3++]=a2[--k2];
				ans[k3++]=a2[--k2];
			}
			else
			{
				ans[k3++]=a1[--k1];
				ans[k3++]=a2[--k2];
			}
		}
		sort(ans,ans+k3);
		for(i=k3-1;i>=0;i--)
		{
			if(i==k3-1)
				printf("%d",ans[i]);
			else
				printf(" %d",ans[i]);
		}
		printf("\n");
	}
	return 0;
}