P83283

轮流取数3

难度 6 级 初三 动态规划入门 博弈 线性
讨论 统计 2通过 3提交 66.7%通过率 旧版界面
时间限制 1 秒 内存限制 128 MB

题目描述

给出N个正整数,AB两个人轮流取数,A先取。每次可以取任意多个数,直到N个数都被取走。每次获得的得分为取的数中的最小值,A和B的策略都是尽可能使得自己的得分减去对手的得分更大。在这样的情况下,最终A的得分减去B的得分为多少。

输入

第一行一个数n,表示数字的数量。

第二行n个数,表示游戏能被取掉的数字。

输出

1≤n≤10^6,1≤k_i≤10^9

样例

样例 1
输入
3
1 3 1
输出
2

提示

来源

POI

Tab 缩进 · 提交后可在下方查看评测状态
请先登录后再提交