交替加乘

NC235687. 交替加乘

描述

有一个长度 $n$ 的数组 $A_1,A_2,A_3,...,A_n$ ，可以对数组 $A$ 进行任意排列。问：经过排列后，数组 $A$ 进行"交替加乘”运算得到最大的结果是多少。

“交替加乘”运算规则： $A_1$ 和 $A_2$ 相加，相加后结果乘以 $A_3$ ，相乘后结果再加上 $A_4$ ，相加后结果乘以 $A_5$ ，以此类推直到 $A_n$ 。

数组 $A$ 长度为 $7$ ，计算如： $(((A_1+A_2)\times A_3+A_4)\times A_5+A_6)\times A_7$

数组 $A$ 长度为 $8$ ，计算如： $(((A_1+A_2)\times A_3+A_4)\times A_5+A_6)\times A_7+A_8$

求取模前的最大结果，输出对 $10^9+7$ 取模。

输入描述

第一行包括一个整数 $n$ $(2\le n\le10^5)$ ，表示数组的长度。

第二行包括 $n$ 个整数，分别表示 $A_1,A_2,...,A_n$ ， $(1\le A_i\le10^9)$ 。

输出描述

输出一行，包含一个整数，表示  。

示例1

输入:

3
3 2 2

输出:

说明:

取得最大结果的数组 $A$ 一种排列为 $[2,2,3]$ ，最大结果是 $(2+2)\times 3=12$ ，对 $10^9+7$ 取模，输出 $12$ 。

上次编辑到这里，代码来自缓存点击恢复默认模板

Python3 解法, 执行用时: 190ms, 内存消耗: 16332K, 提交时间: 2022-04-22 21:07:40

n = int(input())
s = input().split()
arr = []
mod = 10**9+7
for i in range(0,n):
    arr.append(int(s[i]))
arr.sort()
ret = arr[n//2]
i = n//2-1
j = n//2+1
while i>=0 or j<n:
    if i >= 0:
        ret+=arr[i]
        ret%=mod
    if j < n:
        ret*=arr[j]
        ret%=mod
    i-=1
    j+=1
print(ret)

C++(clang++ 11.0.1) 解法, 执行用时: 57ms, 内存消耗: 856K, 提交时间: 2022-10-14 21:20:34

#include<bits/stdc++.h>
using namespace std;
int main(){
	int mod=(int)1e9+7;
	int a;
	cin>>a;
	int b[100008];
	for(int i=0;i<a;i++){
		cin>>b[i];
	}
	sort(b,b+a);
	long long sum=b[a/2];
	for(int i=a/2-1,j=a/2+1;i>=0;i--,j++){
		sum+=b[i];
		if(j<a) sum*=b[j];
		sum%=mod;
	}
    cout<<sum<<endl;
}