题解 | #交替相乘#

题意

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

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

思路

贪心

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

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

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

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

code

$cosecantcosecant$大佬的

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;
		
}