题目描述

给定 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

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#define LL long long 
using namespace std;
int res=1;
int n,k;
int a[100005];
const int Mod=1000000009;
int main(){
    scanf("%d%d",&n,&k);
    for(int i=0;i<n;i++){
        scanf("%d",&a[i]);
    }
    sort(a,a+n);
    int sign=1;
    int l=0;//从前面依次选俩数
    int r=n-1;//从后面依次选俩数
    if(k%2==1){
        res*=a[r--];//k为奇数时，先选一个最大的那个数
        k--;
        if(res<0){//序列A[]全部为负数，k为奇数，乘积和最大必定也是负数，绝对值大的乘积反而小
            sign=-1;
        }
    }
    LL x,y;
    while(k){
        x=(LL)a[l]*a[l+1];y=(LL)a[r]*a[r-1];//怒要忘了加（LL）,因为两个a[]的数可能会爆int,必须得加(LL),不然结果不对
        if(x*sign>y*sign){
            res=x%Mod*res%Mod;
            l+=2;
        }else{
            res=y%Mod*res%Mod;
            r-=2;
        } 
        k-=2;
    }
    printf("%d",res);
    return 0; 
}