欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

Product

程序员文章站 2022-06-01 18:59:04
...

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

#include<iostream>
#include<cstdio>
#include<string>
#include<cstdlib>
#include<cctype>
#include<string.h>
#include<map>
#include<vector>
#include<algorithm>
#include<set>
#include<queue>

using namespace std;

typedef unsigned long long ULL;

const int N=105;

int numz[N],numf[N],ans[N];

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);

    int a,k,n;
    while(cin>>n>>k)
    {
        int num1=0,num2=0;
        while(n--)
        {
            cin>>a;
            if(a>=0)
                numz[num1++]=a;
            else
                numf[num2++]=a;
        }
        sort(numz,numz+num1);
        sort(numf,numf+num2);
        int cnt=0;
        if(k%2==1)
        {
            k--;
            if(num1>0)
                ans[cnt++]=numz[--num1];
            else
            {
                for(int i=num2-1;i>=num2-1-k;i--)
                {
                    printf("%d ",numf[i]);
                }
                continue;
            }
        }
        int j=0;
        for(int i=0;i<k/2;i++)
        {
            int t1=-1;
            int t2=-1;
            if(num1==1&&num2-j==1)
            {
                ans[cnt++]=numz[--num1];
                ans[cnt++]=numf[j++];
            }
            else
            {
                if(num1>1)
                {
                    t1=numz[num1-1]*numz[num1-2];
                }
                if(num2-j>1)
                {
                    t2=numf[j]*numf[j+1];
                }
                if(t1>t2)
                {
                    ans[cnt++]=numz[--num1];
                    ans[cnt++]=numz[--num1];
                }
                else
                {
                    ans[cnt++]=numf[j++];
                    ans[cnt++]=numf[j++];
                }
            }
        }
        sort(ans,ans+cnt);
        for(int i=cnt-1;i>=0;i--)
            printf("%d ",ans[i]);
        printf("\n");
    }
    return 0;

}