【题解】K乘积

佚名 6年前 (2019-04-20) 随笔 501人围观抢沙发百度已收录

题目描述

　　有N个数，每个数的范围是[-50,50]，现在你要从这N个数中选出K个，使得这K个数的乘积最大。

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

输入格式

　　第一行，N和K。 1 <= N <= 50。 1 <= K <= 10。
　　第二行，N个整数。

输出格式

　　一个整数。

输入样例

5 3
6 9 -5 -6 4

输出样例

270

题解

　　容易想到贪心策略：答案必有偶数个负数。则枚举负数数量在乘上剩下的非负数数量即可。这里用前缀积可以更快。

#include <iostream>
#include <algorithm>

#define MAX_N (50 + 5)

using namespace std;

int n, m;
int mid;
long long a[MAX_N];
long long ans = -(1 << 60);

int main()
{
    cin >> n >> m;
    for(register int i = 1; i <= n; ++i)
    {
        cin >> a[i];
        if(a[i] < 0) ++mid;
    }
    sort(a + 1, a + n + 1);
    a[0] = a[n + 1] = 1;
    for(register int i = 1; i <= mid; ++i)
    {
        a[i] *= a[i - 1];
    }
    for(register int i = n; i > mid; --i)
    {
        a[i] *= a[i + 1];
    }
    for(register int i = 0; i <= m && i <= mid; ++i)
    {
        if(m - i > n - mid) continue;
        ans = max(ans, a[i] * a[n - (m - i) + 1]);
    }
    cout << ans;
    return 0;
}