李达

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.9 （C语言代码）

C二级辅导-阶乘数列（C语言代码）

校门外的树（C语言代码）

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

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

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

评论区

精彩推荐

C语言训练-求素数问题（C语言代码）

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

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

Tom数（C语言代码）

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

小九九（C语言描述,不看要求真坑爹）

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

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

小O的乘积（C++代码）

三角形（C语言代码）

李达