【ybt高效进阶6-5-3】魔法珠（博弈论）（模拟）

题目描述

有 $n$ 颗魔法珠，每颗魔法珠有一个权值 $a_i$。现在有两个人 $A$ 和 $B$ 在玩游戏，他们轮流操作，每次操作可以选择一颗魔法珠并将其权值减去 $1$，当某颗魔法珠的权值变为 $0$ 时，它将被移除。游戏结束的条件为所有魔法珠都被移除。假设 $A$ 先手，两人都采用最优策略，求最后 $A$ 的得分与 $B$ 的得分之差。

输入格式

第一行一个整数 $n$，表示魔法珠的数量。

第二行 $n$ 个整数 $a_1,a_2,\dots,a_n$，表示每颗魔法珠的权值。

输出格式

一个整数，表示 $A$ 的得分与 $B$ 的得分之差。

数据范围

$1\leq n\leq 10^5$，$1\leq a_i\leq 10^9$

输入样例

5

2 3 4 5 6

输出样例

-2

算法1

(博弈论) $O(n)$

博弈论

时间复杂度

参考文献

python3 代码

C++ 代码

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码