C++ 题目求助5
本帖最后由 Lynn_oyl 于 2024-3-1 19:05 编辑最值序列
说明
给一个长度为n的序列a_i ，一开始你有一个数A = 0，每次可以从序列中选一个数b，令A = A + b或者A = A * b，每个数都要使用一次，加的次数要和乘的次数近可能相近，要求最大化A，输出A对998244353取模的值
输入格式
第一行为一个整数n，表示序列的长度
第二行为n个整数a_i
描述这个序列,
2≤n≤10^3,1<a_i≤10^9
输出格式
一个非负整数，表示A的最大值对998244353取模的值
样例
输入数据 1
4
3 3 2 4
输出数据 1
60
提示
(2+3)×3×4=60 参考：
MOD = 998244353
def max_value(n, arr):
arr.sort(reverse=True)# 降序排列
if n == 2:# 特殊情况直接处理
return (arr + arr) % MOD
# 计算加法和乘法操作的最佳平衡点
mid = n // 2
if n % 2 == 0:
add_part = sum(arr)# 选择较小的一半数进行加法操作
mul_part = 1
for i in arr[:mid]:# 选择较大的一半数进行乘法操作
mul_part = (mul_part * i) % MOD
else:
# 当元素个数为奇数时，选择一个最佳点使得加法和乘法尽可能平衡
# 通过试验或分析确定这个最佳点，这里假设加入较小的那个数到乘法部分
add_part = sum(arr)
mul_part = arr
for i in arr[:mid]:
mul_part = (mul_part * i) % MOD
return (add_part + mul_part) % MOD
# 示例输入
n = 4
arr =
# 输出结果
print(max_value(n, arr))
页:
[1]