自动搬运

查看原文

来自洛谷，原作者为

	Vsinger_洛天依 天如桜落月摇情 此方凡人入梦月 | 叫我小洛/依依/天依都可以哦 || 逆天依教（其实是粉丝群啦）：1009602220

搬运于2025-08-24 22:41:17，当前版本为作者最后更新于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;
  }