C++
$\color{gold}{— > 蓝桥杯辅导课题解}$
思路:
贪心
$图解:$
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1e5 + 10, mod = 1000000009;
typedef long long ll;
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;
int l = 0, r = n - 1;
int sign = 1; // 标记一下符号
if (k % 2) {
res = a[r --];
k --;
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;
l += 2;
}
else {
res = y % mod * res % mod;
r -= 2;
}
k -= 2;
}
cout << res;
return 0;
}