2018年第九届蓝桥杯【C++省赛B组】【第十题：乘积最大】——贪心算法

时间：2022-09-10 09:49:34

第十题

标题：乘积最大

给定N个整数A1, A2, … AN。请你从中选出K个数，使其乘积最大。

请你求出最大的乘积，由于乘积可能超出整型范围，你只需输出乘积除以1000000009的余数。

注意，如果X<0， 我们定义X除以1000000009的余数是负(-X)除以1000000009的余数。

即：0-((0-x) % 1000000009)

【输入格式】
第一行包含两个整数N和K。  
以下N行每行一个整数Ai。  

对于40%的数据，1 <= K <= N <= 100  
对于60%的数据，1 <= K <= 1000  
对于100%的数据，1 <= K <= N <= 100000  -100000 <= Ai <= 100000  

【输出格式】
一个整数，表示答案。
【输入样例】
5 3 
-100000 -10000 2   
100000  
10000  

【输出样例】
999100009
再例如：
【输入样例】
5 3 
-100000 -100000 -2 -100000 -100000 
【输出样例】
-999999829 暴力贪心一把，只能水部分分的样子。思路：先对数组从小到大排序，因为给出的数有正有负，所以不能直接从后面大的开始直接逐个取(两个最小负数相乘 可能为一个很大的正数)。 如果取的数k是偶数的话，依次取最后面两个数的乘积和最前面两个数的乘积做比较，如果最后面两个数的乘积 更大，自然取这两个数，如果最前面两个数的乘积更大，说明最前面两个数为负数，相乘得到一个大的正数，也 可以取这两个数，直接这样两个两个取直到取到k个为止。 如果取的数k是奇数的话，把排序后的最后那个最大的数a[n-1]拿出来，如果它是正数的话，这个数要取，然后 对剩下k-1个数采取上面为偶数个时的方法依次取(k-1为偶数)；如果a[n-1]为负数或者0的话，说明最大的数 都不为正，且取奇数个数，这个数也要取，可以直接从最大的数开始往前取直到取满k个数，因为最大数为0时其 他数为负数此时乘积为0是最大的，最大数为负数时先取最大数也就是带负号的绝对值最小的数再往小逐个取最 后得到的必定是负的最少(即乘积最大)的。 
#include<bits/stdc++.h>
#define mod 1000000009
using namespace std;
int main() {
  int n, k, a[100005], sum = 0;
  scanf("%d%d", &n, &k);
  for(int i = 0; i < n; i++) {
    scanf("%d", &a[i]);
    if(a[i] == 0) sum++;
  }
  sort(a, a+n);
  if(n - k < sum) printf("0\n");//先考虑特殊情况，选的k个数中必定有0，则结果一定为0 
  else {
    long long ans = 1;
    int l = 0, r = n-1;
    if(k % 2 == 0) {//取偶数个 
      while(k > 0) {
        if(a[r]*a[r-1] > a[l]*a[l+1]) {
          ans *= a[r] * a[r-1] % mod;
          r -= 2;
        }else{
          ans *= a[l] * a[l+1] % mod;
          l += 2;
        }
        k -= 2;
      }
    }else{//取奇数个 
      k -= 1;
      r = n-2;//取出最大的数
      if(a[n-1] > 0) {//最大的数为正数 
        ans *= a[n-1];//先乘上最大数，下面按照取偶数个数的方法来取 
        while(k > 0) {
          if(a[r]*a[r-1] > a[l]*a[l+1]) {
            ans *= a[r] * a[r-1] % mod;
            r -= 2;
          }else{
            ans *= a[l] * a[l+1] % mod;
            l += 2;
          }
          k -= 2;
        }
      }else{//最大的数为0或负数 
        ans *= a[n-1];//逐个从最后面开始取 
        while(k > 0) {
          ans *= a[r];
          r--;
          k--;
        }
      } 
    }
    printf("%lld\n", 0-((0-ans) % mod));
  }
  return 0;
}


标签：

相关文章