对A1~An 排序
(1)k == n 全选
(2)k < n
k是偶数 结果必然非负
1 负数有偶数个 答案>=0
2 负数有奇数个 答案>=0
k是奇数 1 所有数都是负数 答案必然<0
2 至少存在一个非负数 取出这个非负数,问题转化成上面的情况,(k-1为偶数) 结果>=0
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 1e5 + 10, mod = 1000000009;
int n, k;
int a[N];
int main()
{
scanf("%d%d", &n, &k);
for (int i = 0; i < n; i ++ ) scanf("%d", &a[i]);
sort(a, a + n);
int res = 1;
int l = 0, r = n - 1; //双指针
int sign = 1; //正负号, 初始大于0
if (k % 2) //如果k是一个奇数
{
res = a[r -- ]; //先取出正数最大的那一个
k -- ; //取出后k就变成了是偶数的第一种情况
if (res < 0) sign = -1; //如果最右边的数是负数, 那么所有的数都是负数, 符号为-
}
while (k) //一共还要取出k个数相乘
{
long long x = (long long) a[l] * a[l + 1]; //x为最左端的两个数的乘积, 每次都取出两个数(还未取)
long long y = (long long) a[r - 1] * a[r]; //y为最右端的两个数的乘积, 每次都取出两个数(还未取)
//每次取两个数, 保证结果都是>0的
if (x * sign > y * sign) //如果左边的两个数的乘积更大
{
res = x % mod * res % mod;
l += 2; //那么就取出左边的两个数
}
else //如果右边的两个数更大
{
res = y % mod * res % mod;
r -= 2; //那么就取出右边的两个数
}
k -= 2; //还需要k-2个数
}
printf("%d\n", res);
return 0;
}
看了几遍视频+你的题解终于搞懂了hhhh;
思考起来很复杂但其实抓住“先挑出正数最大的”然后循环就好了;