蓝桥杯第九届C++省B组[第10题：乘积最大] —— 贪心算法

绝地灬酷狼 2022-03-12 10:58 140阅读 0赞

[参考博客][Link 1]

去年参加蓝桥杯本来自我感觉良好，结果做题的时候思路乱的要死，最简单的方法能够解决的非想的复杂，导致做到最后一题的时候早已**心烦意乱**。此次再次看到这个题目不得不说作为*最后一个大题*来说**复杂度**倒是比较高的（虽然只是贪心 ），最后花了大概1个多小时理清了本题的思路并解决了，估计比赛要花2 个小时。所以自己还是太弱了 。主要是这类题做得比较少把 。

### 题目: ###

给定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  
**注：对于100000的数据来说，相当于只要你时间复杂度小于 n ^ 3就没问题。蓝桥杯省赛对优化 这方面放得比较松 。而且下面给出的时间复杂度大概是（n \* log(n) + k + n 是小于n \* n的完全可以AC） 。**

> 【输出格式】  
> 一个整数，表示答案。

> 【输入样例】  
> 5 3  
> \-100000  
> \-10000  
> 2  
> 100000  
> 10000

> 【输出样例】  
> 999100009

> 再例如：  
> 【输入样例】  
> 5 3  
> \-100000  
> \-100000  
> \-2  
> \-100000  
> \-100000

> 【输出样例】  
> \-999999829

站在**取到的k个数的角度**，分情况经行考虑：

// 对于取到的k个数中
    	// 1. 如果必须选0， 那么就输出0
    	// 2. 如果前k个数中负数为偶数个，那么就直接计算输出
    	// 3. 如果必须选取奇数个负数， 那么就选取最小的， 即n全部为负数
    	// 4. 如果前k个数中负数为奇数个， 
    	// 那么就可以将一个小负数替换成大正数，或者将小正数替成大负数，取最大

#include<stdio.h>
    #include<stdlib.h>
    #include<math.h>
    long long MAX = 1000000009; 
    
    long long num[10005] = { };
    
    int k = 0;// 选出k个数 
    int n = 0;// 共n个数 
    
    int fu = 0;// 记录选取的负数的个数 
    int frist_z_index = 0;	// 记录第一个正数的位置 
    
    int cmp(const void* a, const void* b){ 
    	return abs(*(int*)b) - abs(*(int*)a);
    } 
    
    int main(){ 
    	
    	
    	scanf("%d", &n);
    	scanf("%d", &k);
    	long long temp = 0;
    	for(int i = 0; i < n; ++i){ 
    		scanf("%lld", &temp);
    		num[i] = temp;
    	}
    	qsort(num, n, sizeof(num[0]), cmp);// 由绝对值从大到小排序
     
    	// 1. 如果必须选0， 那么就输出0
    	// 2. 如果前k个数中负数为偶数个，那么就直接输出
    	// 3. 如果必须选取奇数个负数， 那么就选取最小的， 即n全部为负数
    	// 4. 如果前k个数中负数为奇数个， 
    	// 那么就可以将一个小负数替换成大正数，或者将小正数替成大负数，取最大 
      
    	
    	for(int i = 0; i < k; ++i){ 
    		if(num[i] == 0){ // 第1种情况 必须要选0 
    		/*测数输入样例: 5 3 3 4 0 0 0 */
    			printf("第1种情况: 0");
    			return 0;
    		}else if(num[i] < 0){ 
    			++fu;// 记录负数多少个
    		} 
    	}
    	for(int j = 0; j < n; ++j){ 
    		if(num[j] >= 0){ 
    			frist_z_index = j;// 寻找是否还存在正数可以替换 
    			break;
    		}
    	}
    	
    	if(fu & 1){ // 如果是奇数个负数 
    		if(frist_z_index != 0){  // 第4种情况， 可以替换成偶数个负数 
    		/**测数输入样例 5 3 -1000 100 10 5 -2 4 3 -1000 100 10 -2 */
    			int z1 = 0;
    			int z2 = 0;
    			int f1 = 0;
    			int f2 = 0;
    			// 记录选择中的最小的正负数， 未选择的最大正负数。 
    			for(int i = 0; i < n; i++){ 
    				if(i < k){  
    					if(num[i] > 0){ 
    						z1 = i;
    					}else{ 
    						f1 = i;
    					}
    				}else{ 
    					if(num[i] > 0){ 
    						if(!z2)
    							z2 = i;
    					}else{ 
    						if(!f2)
    							f2 = i;
    					}
    				}
    			}
    			if(!z2){ // 如果不存在可替换的正数或者负数，那么就好办了 
    				num[z1] = num[f2];
    			} else if(!f2){ 
    				num[f1] = num[z2];
    			} else { 
    				if(abs(num[f1]) - num[z2] > num[z1] - abs(num[f2])){ // 如果替换负数结果大 
    					num[z1] = num[f2];  
    				}else{ // 替换正数结果大 
    					num[f1] = num[z2];
    				}
    			}
    			long long ans = 1L;
    			for(int i = 0; i < k; i++){ 
    				ans *= num[i];
    				ans %= MAX;
    			}
    			printf("第4种情况: %lld", ans);
    		}else{ 
    			// n个数都为负数 
    			// 奇数个负数 
    			// 第3种情况 
    			/*测试输入样例 5 3 -100 -10 -1 -1 -1 */
    			long long ans = 1L;
    			for(int j = n - 1, count = 0; count < k; --j){ 
    				ans *= num[j];
    				ans = 0 - ((0 - ans) % MAX);
    				++count;
    			}
    			printf("第3种情况: %lld", ans);
    		}
    	}else{ // 第2种情况 偶数个负数 
    	/*测数输入样例 5 3 -1 -1 -1 -2 2 */
    		long long ans = 1L; 
    		for(int i = 0; i < k; ++i){ 
    			ans *= num[i];
    			ans %= MAX;
    		} 
    		printf("第2种情况: %lld", ans);
    	} 
    	
    	
    
    	return 0;
    }

[Link 1]: https://blog.csdn.net/qq_34202873/article/details/79835790