AcWing 1239. 乘积最大

输入样例

5 3
-100000
-10000
2
100000
10000

输出样例

999100009

输入样例

5 3
-100000
-100000
-2
-100000
-100000

输出样例

-999999829

这道题是典型的贪心，首先我们要考虑一下当选的数为奇数的情况下，若都不是复数，至少选一个非负数，所以有了这个程序

    if(k%2){
    res=g[r--]; k--;if(res<0) sg=-1;}

然后剩下的数，两两取让负数成对取，这样可以保持得出来的数是正值，然后接下来就要判断sg也就是正负的情况了，若sg=-1，说明所有的数都是复数，这样我们两对取得要尽量小故有

LL x=(LL)g[l]*g[l+1];LL y=(LL)g[r]*g[r-1];if(x*sg>y*sg){
    res=(LL)x%M*res%M;l+=2;}else{
    res=(LL)y%M*res%M;r-=2;}

总代码如下

#include<iostream>
#include<algorithm>
using namespace std;
const int N=1e5+10;
const int M=1e9+9;
typedef long long LL;
int g[N];
int main(void)
{
    int n,k,sg=1;cin>>n>>k;for(int i=0;i<n;i++) cin>>g[i];sort(g,g+n);  int l=0,r=n-1;LL res=1;if(k%2){
    res=g[r--]; k--;if(res<0) sg=-1;}while(k){
    LL x=(LL)g[l]*g[l+1];LL y=(LL)g[r]*g[r-1];if(x*sg>y*sg){
    res=(LL)x%M*res%M;l+=2;}else{
    res=(LL)y%M*res%M;r-=2;}k-=2;}cout<<res;
}