P8669 [蓝桥杯 2018 省 B] 乘积最大

诗久桜月 · 2023-10-12 16:31:59 · 题解

• 题意： 在 N 个数中取 K 个数，使这 K 个数的乘积最大，答案对 1000000009 取模。

• 思路： 先把这 N 个数从小到大排序，若 K 为奇数则先乘上最大的一个并把 K-1。若最大的数为负数则记录 f=-1，用贪心从两侧取数并比较与 f 之积，进而求解。

• 代码：

  #include<bits/stdc++.h>
  const long long MOD=1e9+9; 
  using namespace std;
  int main(){
      long long a,c,b[0x66ccff],ans=1;
      int f=1;
      cin>>a>>c;
      for(int i=1;i<=a;i++){
         cin>>b[i];
     }
     sort(b+1,b+a+1);
     if(c%2==1){
         ans*=b[a];
         c--;
         a--;
         if(ans<0){
             f=-1;
          }
     }
    long long left=1,right=a;
    c+=2;
    while(c-=2){
        long long sto=b[left]*b[left+1];
        long long orz=b[right]*b[right-1];
        if(sto*f>=orz*f){
            ans=(sto%MOD)*ans%MOD;
            left+=2;
         }
         else{
              ans=(orz%MOD)*ans%MOD;
              right-=2;
          }
      }
      cout<<ans%MOD;
  }