数组取数游戏中玩家X可获得最大和的高效算法求解

核心结论 #

本题可以通过贪心策略在O(N log N)时间复杂度内解决，完全满足N≤400000的规模要求。

算法步骤 #

• 首先将输入的数组按从小到大排序
• 直接累加排序后数组从下标 N//2 到末尾的所有元素，得到的总和就是X可以拿到的最大值

正确性推导 #

我们可以通过规则拆解验证：

每轮X先选任意元素，Y再取剩余元素排序后下中位数。我们可以通过小范围案例归纳规律：

• N=2时，数组排序后为[a0,a1]，X直接取a1，总和为a1，刚好是a[N//2:]的和
• N=4时，数组排序后为[a0,a1,a2,a3]，X最优选择为先取a3，剩余3个元素的下中位数为a1，Y取a1，最后X取a2，总和为a3+a2 = a[N//2:]的和，和样例0结果一致
  这个策略的本质是：X每次优先取最大的剩余元素，迫使Y只能选择更小的中位数，最终X可以稳定拿到排序后所有偏大的N/2个元素的总和，不存在更优的选择。

代码示例（Python） #

def max_x_sum():
    import sys
    input = sys.stdin.read
    data = input().split()
    n = int(data[0])
    a = list(map(int, data[1:n+1]))
    a.sort()
    return sum(a[n//2:])

print(max_x_sum())

使用sys.stdin.read批量读取输入是为了适配大输入场景，避免4e5量级数据时出现输入超时问题。

复杂度说明 #

• 时间复杂度：排序步骤为O(N log N)，求和步骤为O(N)，整体为O(N log N)，完全可以通过N=4e5的测试用例
• 空间复杂度：O(1)额外空间（不计入输入存储的空间）

内容的提问来源于stack exchange，提问作者Onkar Hanchate