题目描述

给定 N 个整数 A1,A2,…AN。

请你从中选出 K 个数，使其乘积最大。

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

注意，如果 X<0， 我们定义 X 除以 1000000009 的余数是负(−X)除以 1000000009 的余数，即：0−((0−x)%1000000009)
输入格式
第一行包含两个整数 N 和 K。

以下 N 行每行一个整数 Ai。

输出格式

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

数据范围

1≤K≤N≤105,
−105≤Ai≤105

输入样例1：

5 3
-100000
-10000
2
100000
10000

输出样例1：

999100009

输入样例2：

5 3
-100000
-100000
-2
-100000
-100000

输出样例2：

-999999829

主要考点

贪心

主要思路

step 1. 对Ai~An排序

step 2. 分类讨论：
    1) k == n, 直接算

    2) k < n , 再分类
        1) k为偶数, 结果必然为负，分类讨论：
            a. 负数有偶数个, 则 res >= 0
            b. 负数有奇数个, 则选偶数个奇数, 则 res >= 0

        2) k为奇数, 分类讨论：
            a. 所有数均为负数, res < 0
            b. 至少存在一个非负数,先选择最大的那个,然后再从k - 1个中选(k - 1 为偶数,回到上一种情况),res >= 0

C ++ 代码

#include <iostream>
#include <algorithm>

using namespace std;
typedef long long LL;
const int N = 1e5 + 10, mod = 1000000009;

int n, k;
int a[N];

int main(){
    cin >> n >> k;
    for(int i = 0; i < n; i ++) cin >> a[i];

    sort(a, a + n);

    int res = 1, sign = 1;
    int l = 0, r = n - 1; 

    if(k % 2){  // k为奇数的情况
        res = a[r];
        r --, k --;
        if(res < 0) sign = -1;  //判断最大值的符号， sign = -1, 表示最终结果为负
    }

    while(k){
        LL x = (LL)a[l] * a[l + 1], y = (LL)a[r - 1] * a[r];
        if(x * sign > y * sign){
            res = x % mod * res % mod;
            l += 2;
        }
        else{
            res = y % mod * res % mod;
            r -= 2;
        }
        k -= 2;
    }

    printf("%d\n", res);

    return 0;
}