P4805.第1题-这是什么博弈
题目内容
笨蛋同学正在和天才同学博弈。现在在桌子上有 n 份食物，n 为偶数。第i份食物的美味度为ai。
由笨蛋同学先手，笨蛋同学每次会拿走当前桌子上美味度最高的食物。随后，天才同学为了达成自己的目标，会从桌上剩余的食物中选择并拿走一份；两人交替行动，直至桌上无食物。
天才同学的目标是：让笨蛋同学吃到的食物总美味度与自己吃到的食物总美味度的差值尽量小（可能为负数）。天才同学绝顶聪明。
请问在两人都采取各自的策略下，这个差值最小是多少？
输入描述
每个测试文件均包含多组测试数据：第一行输入一个整数 T(1≤T≤2×105)，代表数据组数。
每组测试数据描述如下：
- 第一行输入一个正整数 n(2≤n≤2×105)，表示食物份数。保证n为偶数。
- 第二行输入 n 个正整数 a1,a2,…,an（1≤ai≤109)，表示食物的美味度。
除此之外，保证单个测试文件的 n之和不超过4×105。
输出描述
对于每一组测试数据，新起一行。输出一个整数，表示最小的差值。
样例1
输入
3
2
10 20
4
2 1 5 8
6
1 1 1 1 1 1
输出
10
4
0
说明
对于第一组样例：
- 笨蛋同学先手，取走美味度为 20 的食物；
- 天才同学取走剩下美味度为 10 的食物；
- 最终差值为 20−10=10。
