POJ 3399 Product k個の正負の整数を探して、積の最大のを探します


Product
Time Limit: 1000MS
 
Memory Limit: 65536K
Total Submissions: 2813
 
Accepted: 672
 
Special Judge
Description
There is an array of N integer numbers in the interval from -30000 to 30000. The task is to select K elements of this array with maximal possible product.
Input
The input consists of N + 1 lines. The first line contains N and K (1 ≤ K ≤ N ≤ 100) separated by one or several spaces. The others contain values of array elements.
Output
The output contains a single line with values of selected elements separated by one space. These values must be in non-increasing order.
Sample Input
4 2
1
7
2
0

Sample Output
7 2

問題はあなたにn個の数字をあげて、それからk個の数字を選んで、乗じます.どの数字の積が一番大きいかを探します.
私は貪欲な考えを使っています. 
絶対値が一番大きいから探します.負数であれば、ペアになってans配列に加算する.
ansが1つの数しか入れられない場合は、判断して、具体的にコードの注釈を見ましょう.
最後にk数字の乗算エネルギーが0以上であることが見つからなければ、前のn個の絶対値の最小数を出力すればよい.負の数かゼロ未満に違いないので、productをできるだけ小さくします.
#include<stdio.h>
#include<algorithm>
using namespace std;
int abb(int a)
{
	if(a<0)
		return -a;
	else
		return a;
}
int cmp(int a,int b)
{
	return abb(a)<abb(b);
}
int main()
{
	int n,k,i,j,flag;
	int a[200],z[200],f[200],tem,ttt[5],ans[200],l,x;
	while(scanf("%d%d",&n,&k)!=EOF)
	{
		for(i=0;i<n;i++)
		{
			scanf("%d",&a[i]);
		}
	 
		l=0; 
		sort(a,a+n,cmp);
		flag=0;
		for(i=n-1;i>=0&&l<k;i--)//   k  ,         ,         .
		{
			if(a[i]<0&&flag==0)//flag      ttt      
			{
				ttt[0]=a[i];
				flag=1;
			}
			else if(a[i]<0&&flag==1&&l+2<=k)//          k    ,   l+2<=k  
			{
				ans[l++]=ttt[0];
				ans[l++]=a[i];
				flag=0;
			}
			else if(a[i]<0&&flag==1&&l+2>k) //l+2>k          ,      k,        
			{
				for(j=i-1;j>=0;j--)//                    
				{
					if(a[j]>=0)
						break;
				}
				for(x=l-1;x>=0;x--)//     ans              
				{
					if(ans[x]>=0)
						break;
				}
				if(j>=0&&x>=0)//        
				{
					if(a[j]*ans[x]<ttt[0]*a[i])//             ,          .    ans  
					{
						ans[l++]=ttt[0];
		          		ans[x]=a[i];
					}
					else
					{
						ans[l++]=a[j];
					}
				}
				flag=0;
			}
			else if(a[i]>=0)
				ans[l++]=a[i];
		}
		if(l<k)//    k               ,          k  
		{
			for(i=0;i<k;i++)
			{
				ans[i]=a[i];
			}
		}
		sort(ans,ans+k);
		for(i=k-1;i>=0;i--)
		{
			if(i==k-1)
				printf("%d",ans[i]);
			else
			printf(" %d",ans[i]);
		}
		puts("");
	}
	return 0;
}