acwing1239. 乘积最大

题目

题解

• 整体思路:
  该题的题解是整理了一下 y总视频里面讲解思路,希望对看完视频还不大理解的同学有点帮助
  首先我们知道 如果 k == n ,那么就证明所有的数字是全部都选,
  如果 k < n , 那么就要思考怎样去选择了:
  1.k 如果是偶数的话,选出来的结果一定是非负数 , 原因如下:
  (1) 负数的个数是偶数个的话,负负得正,那么一定是非负数
  (2) 负数的个数如果是奇数个的话,那么我们就只选偶数个绝对值最大的负数
  2.k 如果是奇数个的话,
  (1)所有的数字如果都是负数,那么选出来的结果也一定都是负数
  (2)否则的话,则一定至少有 1个非负数, 那么我们将最大的数取出来, 此时要选的个数就是 k–,
  k-- 是偶数,那么就又转化为 k-- 是偶数的情况思考

作者：大厂狗狗
链接：https://www.acwing.com/solution/content/8724/

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N=100010;
const int MOD=1000000009;
int a[N],n,k;
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 sign=1;
    int l=0,r=n-1;
    if(k%2){
        res=a[r--];
        k--;
        if(res<0)sign=-1;
    }
    while(k){
        long long x=(long long)a[l]*a[l+1],y=(long long)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;
    }
    printf("%d\n",res);
    
    return 0;
}