解题思路
先把题目中双方对 A−B 的影响拆开来看。
设某个位置 i 的权值为：
xi=ai−bi
P4677.第1题-回合制游戏
题目内容
给定两个长度均为 n 的整数数组 a={a1,a2,…,an} 与b={b1,b2,…,bn}，进行一场回合制对抗游戏，规则如下：
- 共有 n个位置1∼n，每个位置只能被选择一次，由 Alice 先手，两人轮流行动；
- 轮到 Alice 行动时：选择一个未被选择的位置 i，获得收益 ai 并支付代价 bi，本回合净收益为 (ai−bi)；
- 轮到 Bob 行动时：选择一个未被选择的位置i，获得收益 bi 并支付代价 ai，本回合净收益为 (bi−ai)；
- 所有位置被选择后游戏结束，设 Alice 的总净收益为A，Bob 的总净收益为B；
- 两人均采取最优策略：Alice 希望最大化 A−B，Bob 希望最小化 A−B，双方完全理性，总是选择对自己最有利的行动。
请输出在最优博弈下的分差A−B。
输入描述
每个测试文件包含多组测试数据：
第一行输入一个整数T(1≤T≤105)，表示测试数据组数；
每组测试数据：
-
第一行输入一个整数 n(1≤n≤2×105)，表示数组长度；
-
第二行输入n个整数a1,a2,…,an(∣ai∣≤109)；
-
第三行输入n 个整数b1,b2,…,bn(∣bi∣≤109)；
保证所有测试数据中n 的总和不超过 3×105。
输出描述
对于每组测试数据，输出一行一个整数，表示在双方都采取最优策略时的分差A一B。
样例1
输入
3
3
3 1 2
2 2 2
2
1 10
10 1
4
5 1 1 1
1 4 4 4
输出
0
0
-5
