← 返回题目列表

AtCoder · abc088_b

B. 两人纸牌游戏

中文机器翻译题面 查看原题

分数: 200 点

问题陈述

我们有 N 卡。一个数字 a_i 写在 i第一张卡。
Alice 和 Bob 将使用这些卡片玩游戏。在这个游戏中,爱丽丝和鲍勃交替拿一张牌。爱丽丝先走。
当两名玩家拿走所有牌时,游戏结束,每个玩家的分数是他/她所拿的牌上写的数字之和。当两个玩家都采取最优策略来最大化他们的分数时,找到爱丽丝的分数减去鲍勃的分数。

约束

  • N 是介于 1 和 100 (含)。
  • a_i \ (1 \leq i \leq N) 是介于 1 和 100 (含)。

输入

输入由标准输入按以下格式给出:

N
a_1 a_2 a_3 ... a_N

输出

当两个玩家都采取最优策略来最大化他们的分数时,打印 Alice 的分数减去 Bob 的分数。


示例输入 1

2
3 1

示例输出 1

2

首先,Alice 会拿着卡片 3。然后,鲍勃将拿走卡片 1。 他们的分数之差将是 3 - 1 = 2.


示例输入 2

3
2 7 4

示例输出 2

5

首先,Alice 会拿着卡片 7。然后,鲍勃将拿走卡片 4。最后,爱丽丝将拿走卡片 2。他们的分数之差将是 7 - 4 + 2 = 5。他们的分数之差将是 3 - 1 = 2.


示例输入 3

4
20 18 2 18

示例输出 3

18