贪心

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 100010;
int a[N];
int n,k;
typedef long long LL;
LL mod = 1e9 + 9;
int main()
{
    cin >> n >> k;
    for(int i = 0;i < n;i++) cin >> a[i];
    sort(a,a + n);
    int res = 1;
    int l = 0,r = n - 1;
    int sign = 1;
    //如果k是奇数，那么先把最大的数给取了，然后再转化成k为偶数来处理
    if(k % 2 == 1)
    {
        res = a[r--];
        k--;
        if(res < 0) //如果所有数都为负数
        {
            sign = -1;
        }
    }

    while(k)
    {
        //利用双指针算法，一头一尾
        LL x = (LL)a[l] * a[l + 1],y = (LL)a[r - 1] * a[r];
        if(x * sign > y * sign)// //sign是-1, 返回的是x,y中较小的,  sign是1, 返回x,y中较大的
        {
            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;
    }
    cout << res << endl;
    return 0;
}