374: [蓝桥杯2018初赛]乘积最大

时间限制: 1 Sec 内存限制: 256 MB

题目描述

给定N个整数A1, A2, ... AN。请你从中选出K个数，使其乘积最大。
请你求出最大的乘积，由于乘积可能超出整型范围，你只需输出乘积除以1000000009的余数。
注意，如果X<0，我们定义X除以1000000009的余数是负(-X)除以1000000009的余数。
即：0-((0-x) % 1000000009)

输入

第一行包含两个整数N和K。
以下N行每行一个整数Ai。
1 <= K <= N <= 100000 -100000 <= Ai <= 100000

输出

一个整数，表示答案。

样例输入

样例输出

999100009

注意取模时得巨坑

  1 /*
  2 	首先我们知道 如果 k == n ,那么就证明所有的数字是全部都选,
  3              如果 k < n , 那么就要思考怎样去选择了:
  4 1.k 如果是偶数的话,选出来的结果一定是非负数 , 原因如下:
  5              (1) # 负数的个数是偶数个的话,负负得正,那么一定是非负数
  6              (2) # 负数的个数如果是奇数个的话,那么我们就只选偶数个绝对值最大的负数
  7 2.k 如果是奇数个的话,
  8              (1)# 所有的数字如果都是负数,那么选出来的结果也一定都是负数
  9              (2)# 否则的话,则一定至少有 1个非负数, 那么我们将最大的数取出来, 此时要选的个数就是 k--,
 10                 # k-- 是偶数,那么就又转化为 k-- 是偶数的情况思考
 11 
 12 
 13 */
 14 #include <iostream>
 15 #include <algorithm>
 16 using namespace std;
 17 
 18 using ll = long long;
 19 
 20 constexpr size_t maxn = 1e5 + 5;
 21 
 22 ll mod = 1000000009;
 23 ll a[maxn];
 24 int main()
 25 {
 26 	ll n,k;
 27 	cin >> n >> k;
 28 	for(ll i = 0; i < n; ++ i)cin >> a[i];
 29 	sort(a,a+n);
 30 	ll res = 1;
 31 	ll l = 0, r = n-1;
 32 	ll sign = 1;
 33 	if(k&1){
 34 		res = a[r];
 35 		r--;
 36 		k--;
 37 		if(res < 0)sign = -1;//最大得数都是负数就说明全为负数则变号
 38 	}
 39 	while(k){
 40 		ll x = a[l] * a[l+1], y = a[r] * a[r-1];
 41 		if(x * sign > y * sign)
 42         {
 43             res = x % mod * res % mod; // 需要注意的是 :不可以写成(x * res) % mod ,也不可以写成是 res % mod * x % mod
 44                                        // 因为x最大是 10^10，如果不先取模的话，和res相乘的结果最大是 10^19,会暴long long。            
 45             l += 2; // 指针移动                                 
 46         }
 47 
 48 		else{
 49 			res = y % mod * res % mod;
 50             r -= 2;
 51 		}
 52 		k -= 2;
 53 	}
 54 	cout << res << endl;
 55 	return 0;
 56 }

追求吾之所爱