题目描述

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

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

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

注意，如果 X<0， 我们定义 X 除以 1000000009 的余数是负(−X)除以 1000000009 的余数，即：0−((0−x)%1000000009)

样例

输入样例1：
5 3
-100000
-10000
2
100000
10000
输出样例1：
999100009
输入样例2：
5 3
-100000
-100000
-2
-100000
-100000
输出样例2：
-999999829

# 整体思路


该题的题解是整理了一下 y总视频里面讲解思路,希望对看完视频还不大理解的同学有点帮助
首先我们知道 如果 k == n ,那么就证明所有的数字是全部都选,
             如果 k < n , 那么就要思考怎样去选择了:
1.k 如果是偶数的话,选出来的结果一定是非负数 , 原因如下:
             (1) # 负数的个数是偶数个的话,负负得正,那么一定是非负数
             (2) # 负数的个数如果是奇数个的话,那么我们就只选偶数个绝对值最大的负数
2.k 如果是奇数个的话,
             (1)# 所有的数字如果都是负数,那么选出来的结果也一定都是负数    
             (2)# 否则的话,则一定至少有 1个非负数, 那么我们将最大的数取出来, 此时要选的个数就是 k--, 
                # k-- 是偶数,那么就又转化为 k-- 是偶数的情况思考

参考文献: y总视频

C++ 代码

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;

typedef long long LL ;
const int N = 100010 , mod = 1000000009 ;
int a[N];


int main()
{
    int n , k ;
    scanf("%d%d",&n,&k);
    for(int i = 0 ; i < n ; i ++) scanf("%d",&a[i]);

    sort(a,a + n);

    LL res = 1 ; //乘积初始化
    int l = 0 , r = n - 1 ;//双指针初始化
    int sign = 1 ; // 符号初始化

    //由于4种情况除了 k 是奇数且 k < n 的时候需要特判一下处理一下符号 ,其他的时候都可以转化为双指针做法
    //k 是奇数是先选出最大的数, k-- 就是偶数,两边再同时取对,转化成相同的双指针做法
    if(k % 2 )
    {
        res =  a[r]; // 取出最大的一个数
        r -- ; //右指针移动
        k -- ; //个数减1

        if(res < 0) sign = -1;  // 如果最大值都是负数,就证明全是负数,那么符号要发生改变
    }
    while(k) // 双指针做法
    {
        LL x = (LL)a[l] * a[l + 1] , y = (LL)a[r] * a[r - 1];//两边同时取对
        //选择更大的一对,和归并排序思路相近
        if(x * sign > y * sign)
        {
            res = x % mod * res % mod; // 需要注意的是 :不可以写成(x * res) % mod ,也不可以写成是 res % mod * x % mod
                                       // 因为x最大是 10^10，如果不先取模的话，和res相乘的结果最大是 10^19,会暴long long。            
            l += 2; // 指针移动                                 
        }
        else 
        {
            res = y % mod * res % mod; 
            r -= 2; 
        }
        k -= 2; 
    }
    printf("%lld",res);
    return 0;
}