乘积最大
策略:贪心+排序+双指针
1. 当k == n;
没啥可说全选即可
2. 当k < n;
- 若k%2 == 0
结果必然非负
1️⃣负数有偶数个,结果>=0
2️⃣负数有奇数个,结果舍去一个负数还为>=0因此,我们可以直接舍弃一个奇数还按偶数来搞
- 若k%2 == 1
1️⃣所有数均为负数,结果必然 < 0
2️⃣至少存在一个非负数,结果 >= 0
具体代码
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>
#define N 100010
#define mod 1000000009
using namespace std;
typedef long long LL;
int n,k;
int q[N];
int main()
{
scanf("%d%d",&n,&k);
for(int i = 0;i < n;i ++) scanf("%d",&q[i]);
//先排序
sort(q,q+n);
int res = 1;
int l = 0 , r = n - 1;
int sign = 1;
if(k%2) //判断是奇数,拿出最后一个数,按偶数来操作
{
res = q[r --];
k --;
if(res < 0) sign = -1; //若最后一个数也是负数,直接变符号
}
while(k)
{
LL x = (LL)q[l] * q[l+1] , y = (LL)q[r-1] * q[r];
if(x * sign > y *sign)
{
res = x % mod * res % mod;
l += 2;
}
else
{
res = y % mod * res % mod;
r -= 2;
}
k -= 2;
}
printf("%d\n",res);
return 0;
}