[已解决]C++ 题目求助5

Lynn_oyl · 发表于 2024-3-1 19:05:15

本帖最后由 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

最佳答案

月排行榜 / 总排行榜

不二如是

2024-3-1 19:05:16

参考：

MOD = 998244353
def max_value(n, arr):
arr.sort(reverse=True) # 降序排列
if n == 2: # 特殊情况直接处理
return (arr[0] + arr[1]) % MOD
# 计算加法和乘法操作的最佳平衡点
mid = n // 2
if n % 2 == 0:
add_part = sum(arr[mid:]) # 选择较小的一半数进行加法操作
mul_part = 1
for i in arr[:mid]: # 选择较大的一半数进行乘法操作
mul_part = (mul_part * i) % MOD
else:
# 当元素个数为奇数时，选择一个最佳点使得加法和乘法尽可能平衡
# 通过试验或分析确定这个最佳点，这里假设加入较小的那个数到乘法部分
add_part = sum(arr[mid+1:])
mul_part = arr[mid]
for i in arr[:mid]:
mul_part = (mul_part * i) % MOD
return (add_part + mul_part) % MOD
# 示例输入
n = 4
arr = [3, 3, 2, 4]
# 输出结果
print(max_value(n, arr))

复制代码

跳转到最佳答案楼层

不二如是 · 发表于 2024-3-1 19:05:16

参考：

MOD = 998244353
def max_value(n, arr):
arr.sort(reverse=True) # 降序排列
if n == 2: # 特殊情况直接处理
return (arr[0] + arr[1]) % MOD
# 计算加法和乘法操作的最佳平衡点
mid = n // 2
if n % 2 == 0:
add_part = sum(arr[mid:]) # 选择较小的一半数进行加法操作
mul_part = 1
for i in arr[:mid]: # 选择较大的一半数进行乘法操作
mul_part = (mul_part * i) % MOD
else:
# 当元素个数为奇数时，选择一个最佳点使得加法和乘法尽可能平衡
# 通过试验或分析确定这个最佳点，这里假设加入较小的那个数到乘法部分
add_part = sum(arr[mid+1:])
mul_part = arr[mid]
for i in arr[:mid]:
mul_part = (mul_part * i) % MOD
return (add_part + mul_part) % MOD
# 示例输入
n = 4
arr = [3, 3, 2, 4]
# 输出结果
print(max_value(n, arr))

复制代码

账号		自动登录	找回密码
密码			立即注册