当前位置：网站首页>[nk]牛客月赛48 D

[nk]牛客月赛48 D

2022-04-23 02:07:00 【RISE_lower】

题意

给定一个 $n$ 长度的 $a []$ ,你可以任意排列 $a []$

最后使得交替相乘最大(这个是什么看题)

思路

贪心

显然的 (当然不是,我只会赛后口嗨

显然我们让和最大的数先加,那么后面计算乘法的时候,贡献是最大的

因此我们考虑 (大的*大的)*大的+小的

$400$ 多个人过的贪心,感觉这个贪心好怪

code

$c o s e c a n t$ 大佬的

const int N = 1e5+10 ,mod =  1e9+7;

int a[N],n,b[N];

void solve(){
    
	cin>>n;
	for(int i=1;i<=n;i++) cin>>b[i];
	sort(b+1,b+1+n);
	
	int j = 1;
	//偶数 用来加 (小的放后面加)
	for(int i=n/2*2;i>=2;i-=2)  a[i] = b[j++];
	//奇数 用来乘 (大的放前面乘)
	for(int i=1;i<=n;i+=2) a[i] = b[j++];
	
	int s = a[1];
	for(int i=2;i<=n;i++){
    
		if(i&1){
    //奇数的时候 是相乘
			s = 1ll*s*a[i]%mod;
		}else{
    //偶数的时候是相加
			s = (s+a[i])%mod;
		}
	}
	cout<<s<<endl;
		
}

版权声明
本文为[RISE_lower]所创，转载请带上原文链接，感谢
https://blog.csdn.net/qq_34364611/article/details/124355266

当前位置：网站首页>[nk]牛客月赛48 D

[nk]牛客月赛48 D

题意

思路

code

边栏推荐

猜你喜欢

随机推荐