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
Sample Output
問題はあなたにn個の数字をあげて、それからk個の数字を選んで、乗じます.どの数字の積が一番大きいかを探します.
私は貪欲な考えを使っています.
絶対値が一番大きいから探します.負数であれば、ペアになってans配列に加算する.
ansが1つの数しか入れられない場合は、判断して、具体的にコードの注釈を見ましょう.
最後にk数字の乗算エネルギーが0以上であることが見つからなければ、前のn個の絶対値の最小数を出力すればよい.負の数かゼロ未満に違いないので、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;
}