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

Lynn_oyl

最值序列
说明
给一个长度为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))

跳转到最佳答案楼层

不二如是

参考：

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))