2018年第九届蓝桥杯省赛-J.乘积最大

原题链接

题面

给定 N 个整数 $A_1, A_2, \cdots A_N$。请你从中选出 K 个数，使其乘积最大。

请你求出最大的乘积，由于乘积可能超出整型范围，你只需输出乘积除以 10⁹+9 的余数。

注意，如果 X<0，我们定义 X 除以 10⁹+9 的余数是负(-X)除以 10⁹+9 的余数。

即：$0-((0-x) \% 1000000009)$。

输入描述

第一行包含两个整数 N,K。

以下 N 行每行一个整数 $A_i$。

其中，$1 \leq K \leq N \leq 10^5， -10^5 \leq A_i \leq 10^5$。

输出描述

输出一个整数，表示答案。

输入样例

5 3
-100000
-10000
2
100000
10000

输出样例

999100009

题解

数学，分类讨论

本人的做法有点繁杂，仅提供给大家一个思路，望大家去看看其他的优质解法！

对于负数，两个负数相乘能变成一个整数，则我们每次选两个未使用的最小的负数相乘同两个未使用的最大的整数相乘做比较，那一对较大，就使用那一对。但当剩下三个数要选，且正数个数大于等于3，负数个数大于等于 2 的时候，则需要去比较最大的正数去乘两个最小的负数的结果大，还是三个最大的正数相乘结果大，进行最优的选择。

具体见代码。

代码

#include<bits/stdc++.h>

using namespace std;

typedef long long LL;
const int N = 1e5 + 5, MOD = 1e9 + 9;
int n, K, z, a[N];  //z为 0 的个数
LL s = 1;
vector<LL> fs, zs; //负数和正数数组

void calc() {
    int i = fs.size() - 1, j = zs.size() - 1; //负数下标i，正数下标j
    int k = K & 1 ? K - 3 : K;  //奇数的话需留下剩余3个进行特判
    int t = 0;
    while (t < k && i >= 1 && j >= 1) {
        LL mf = fs[i] * fs[i - 1];  //负数对相乘的结果
        LL mz = zs[j] * zs[j - 1];  //正数对相乘的结果

        if (mf >= mz) {    //相等的时候尽量多用负数对
            s = s * (mf % MOD) % MOD;
            i -= 2;
        } else {
            s = s * (mz % MOD) % MOD;
            j -= 2;
        }
        t += 2;
    }
    while (t < k && i >= 1) {    //正数对用完了
        LL v = fs[i - 1] * fs[i] % MOD;
        s = s * v % MOD;
        i -= 2;
        t += 2;
    }
    while (t < k && j >= 1) {    //负数对用完了
        LL v = zs[j - 1] * zs[j] % MOD;
        s = s * v % MOD;
        j -= 2;
        t += 2;
    }

    //偶数情况没有需要算的
    if (k == K) return;

    //剩余3个数没有选出来
    if (j >= 2 && i >= 1) {    //正数个数大于等于3，负数大个数于等于2
        LL mf = fs[i] * fs[i - 1] * zs[j];
        LL mz = zs[j] * zs[j - 1] * zs[j - 2];
        s = s * (max(mf, mz) % MOD) % MOD;
    } else if (j >= 2) {
        LL v = zs[j] * zs[j - 1] * zs[j - 2] % MOD;
        s = s * v % MOD;
    } else {
        LL v = zs[j] * fs[i] * fs[i - 1] % MOD;
        s = s * v % MOD;
    }
}

int main() {
    cin >> n >> K;
    for (int i = 0; i < n; i++) {
        scanf("%d", &a[i]);
        if (a[i] < 0) fs.push_back(a[i]);
        else if (a[i] > 0) zs.push_back(a[i]);
        else z++;
    }

    sort(fs.begin(), fs.end(), greater<int>());    //负数大到小
    sort(zs.begin(), zs.end());    //正数小到大
    sort(a, a + n);

    if (K == 1) {   //只有1个的情况
        if (zs.size()) cout << zs.back() << endl;
        else if (z) puts("0");
        else printf("%d\n", fs.front());
        exit(0);
    }

    int p = fs.size() / 2;    //负数对数
    if (zs.size() + p * 2 >= K) {    //结果为正数
        if (K & 1) {
            if (zs.size()) calc();  //奇数情况需要至少有一个正数
            else {  //没有正数
                if (z) s = 0;   //有0为0
                else for (int i = 0; i < K; i++) s = s * fs[i] % MOD; //无0为最大的负数相乘
            }
        } else calc();
    } else if (z) {    //存在 0
        s = 0;
    } else {    //不存在0
        for (int i = 0; i < n; i++) s = s * a[i] % MOD;
    }

    cout << s << endl;
    return 0;
}