AcWing
1239. 乘积最大
贪心。首先对所有的数从小到大排序。如果要选取的数的个数k是偶数，那么最终的乘积一定是正数(特殊情况，k==n，即选所有数，此时可以不考虑正负，因为无论怎么选，所有的数都会被选出)；如果要选取的数的个数k是奇数，那么最终的乘积取决于最后选出的一个数(因为前k-1个数的乘积一定可以是正数)，即仅当所有数都为负数时，最后的乘积是负数，这等价于排序后最大的数是负数。仅当在这种情况下，要求前k-1个数的乘积最小。
#include <bits/stdc++.h>
using namespace std;
int n, k;
const int N = 100010, MOD = 1000000009;
int a[N];
typedef long long LL;
int main(){
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin >> n >> k;
for(int i = 0; i <= n - 1; i ++) cin >> a[i];
sort(a, a + n);
int l = 0, r = n - 1;
int cnt = 0, res = 1, sign = 1;
if(k % 2){
res = (res * a[r]) % MOD;
r --, k --;
if(res < 0) sign = -1;
}
while(l <= r && cnt < k){
LL ll = (LL)a[l] * a[l + 1];
LL rr = (LL)a[r] * a[r - 1];
if(ll * sign <= rr * sign){
res = (res * (rr % MOD)) % MOD;
r -= 2;
}
else{
res = (res * (ll % MOD)) % MOD;
l += 2;
}
cnt += 2;
}
cout << res;
return 0;
}