李达

用户名：lida1

访问量：9876

签　名：

等　　级
排　　名	1042
经　　验	3152
参赛次数	5
文章发表	10
年　　龄	0
在职情况	学生
学　　校	信阳农林学院
专　　业

　　自我简介：

TA的其他文章

蓝桥杯算法训练VIP-传纸条-题解（C++代码）
浏览：496

蓝桥杯算法训练VIP-单词接龙-题解（C++代码）
浏览：589

蓝桥杯2013年第四届真题-大臣的旅费-题解（C++代码）官方题解
浏览：364

你可能喜欢

蓝桥杯2018年第九届真题-乘积最大-题解（C++代码）

　　作者: 李达　　　　发表时间：2020-07-15 17:46:24 浏览：971　|　评论：2　

原题链接：蓝桥杯2018年第九届真题-乘积最大

# MarkDown编辑器基本使用说明

**思路：
N个数选K个数 K<=N
N个数中负数size1个，正数size2个，一共size个（不包含0）
将正数分到正数组，负数分到负数组，并将两个数组从小到大排序
1.size<K 
	必须选择0 ans=0

2.size=K 
	2.1 size1是偶数   ans=非0数累乘

2.2 size1不是偶数 
		2.2.1 K<N 说明有0存在，ans=0
		2.2.2 K=N 说明无0存在，ans=全部累乘
		
3.size>K
	3.1 没有正数
		3.1.1 K为偶数，ans=绝对值最大的那K个负数累乘
		3.1.2 K为奇数
			3.1.2.1 size<N ans=0
			3.1.2.2 size=N ans=绝对值最小的那K个负数累乘
	3.2 没有负数 ans=最大的那K个正数累乘
	3.3 有正有负（寻找正数组、负数组的起始游标）
		3.3.1 正数不足k个，假定正数全部选中，剩余偶数个负数，等会再来挪动标尺
			选完正数后，剩余可选个数是奇数，正数先少选一个
		3.3.2 正数多于k个，假定从正数中先选最大的k个
			3.3.2.1 k是偶数 起始游标：正数组 size1-1   负数组 0
			3.3.2.2 k是奇数	起始游标：正数组 size1-2 负数组 0
		双标尺移动
		作用：寻找累乘正数组与负数组哪一段。
		操作：看负数游标起始位置随后的两个负数相乘是否大于正数，游标位置随后的两个正数相乘。
    #include<bits/stdc++.h>
    #define ll long long
    const ll mod = 1e9+9;
    ll ans=1, N, K, sz[100010], k=0;
    int flag=0;
    using namespace std;
    bool cmp(ll a,ll b){
    	return a>b;
    }
    int main()
    {
    	cin>>N>>K;
    	for(int i=0; i<N; i++){
    		cin>>sz[i];
    		if(sz[i]>0) flag=1;
    	}
    	if(flag==0){
    		if(K%2==1){
    		sort(sz,sz+N,cmp);
    		long long sum=1;
    		for(int i=0;i<K;i++)
    		{
    			//cout<<sz[i];
    			sum*=sz[i];
    			sum%=mod;
    		}
    		cout<<sum;
    		return 0;
    		}
    		else{
    		sort(sz,sz+N);
    		long long sum=1;
    		for(int i=0;i<K;i++)
    		{
    			//cout<<sz[i];
    			sum*=sz[i];
    			sum%=mod;
    		}
    		sum%=mod;
    		cout<<sum;
    		return 0;
    		}
    		
    	} 
    		
    	
    	sort(sz, sz+N);
    	ll l=0, r=N-1;
    	
    	while(k!=K)
    	{
    		if(sz[l]*sz[l+1] > sz[r]*sz[r-1] && K-k >= 2)
    		{
    			ans = ((ans * sz[l])%mod * sz[l+1])%mod;
    			l = l + 2;
    			k += 2;
    		}
    		else
    		{
    			ans = (ans * sz[r])%mod;
    			r = r - 1; 
    			k++;
    		}
    	}
    	cout<<ans;
    	
    	return 0;
    }

0.0分

5 人评分

看不懂代码？想转换其他语言的代码？或者想问其他问题？试试问问AI编程助手，随时响应你的问题：

　　评论区

墨

k是一定小于或等于n的，不必担心k大于n的情况（看看数据规模啊）

2022-04-11 22:18:35

陈正磊

强

2020-10-13 11:26:54

李达

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题8.4 （C语言代码）

C语言程序设计教程（第三版）课后习题6.7 （C语言代码）

C语言程序设计教程（第三版）课后习题6.4 （C语言代码）

不知道哪里错了

printf基础练习2 （C语言代码）

蓝桥杯2018年第九届真题-乘积最大-题解（C++代码）

评论区

精彩推荐

矩阵加法（C语言代码）

1124题解

星期判断机（C语言代码）

时间转换（C语言代码）

C语言程序设计教程（第三版）课后习题6.10 （C语言代码）

C语言程序设计教程（第三版）课后习题3.7 （C语言代码）

最好的，

10月月赛题解

【出圈】（C++代码）简单循环

非常简单的算法，题解1049：C语言程序设计教程（第三版）课后习题11.1 （C语言代码）

李达

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题8.4 （C语言代码）

C语言程序设计教程（第三版）课后习题6.7 （C语言代码）

C语言程序设计教程（第三版）课后习题6.4 （C语言代码）

不知道哪里错了

printf基础练习2 （C语言代码）

蓝桥杯2018年第九届真题-乘积最大-题解（C++代码）

评论区

精彩推荐

矩阵加法 （C语言代码）

1124题解

星期判断机 （C语言代码）

时间转换 （C语言代码）

C语言程序设计教程（第三版）课后习题6.10 （C语言代码）

C语言程序设计教程（第三版）课后习题3.7 （C语言代码）

最好的，

10月月赛题解

【出圈】 （C++代码）简单循环

非常简单的算法，题解1049：C语言程序设计教程（第三版）课后习题11.1 （C语言代码）

　　评论区

矩阵加法（C语言代码）

星期判断机（C语言代码）

时间转换（C语言代码）

【出圈】（C++代码）简单循环