#P18627. Soldier Game
Soldier Game
Soldier Game
DreamGrid 和 BaoBao 正在玩一个有 名士兵的游戏。士兵按顺序编号为 ,第 名士兵的战斗力为 。
他们要将所有士兵分成若干队,满足:
- 每队只能包含一名或两名士兵;
- 每名士兵必须且只能属于一队;
- 如果第 名和第 名士兵属于同一个两人队,那么必须有 ,即两人原编号相邻。
一支队伍的战斗力是队员战斗力之和。为了公平,他们希望最强队伍与最弱队伍的战斗力之差尽可能小。
请计算这个差值的最小可能值。士兵的战斗力可以是负数。
输入格式
第一行包含整数 ,表示测试用例数。
每个测试用例的第一行包含整数 。
第二行包含 个整数 。
数据范围
- ;
- ;
- 一个输入文件中,所有测试用例的 之和不超过 。
输出格式
对每个测试用例输出一行,包含最强队伍与最弱队伍战斗力差值的最小可能值。
样例输入 1
3
5
-1 4 2 1 1
4
1 3 2 4
1
7
样例输出 1
1
2
0
样例解释
第一个测试用例的全部八种划分如下。斜杠分隔不同队伍。
| 队伍划分 | 最强与最弱之差 |
|---|---|
| [-1] / [4] / [2] / [1] / [1] | 5 |
| [-1] / [4] / [2] / [1,1] | |
| [-1] / [4] / [2,1] / [1] | |
| [-1] / [4,2] / [1] / [1] | 7 |
| [-1,4] / [2] / [1] / [1] | 2 |
| [-1] / [4,2] / [1,1] | 7 |
| [-1,4] / [2] / [1,1] | 1 |
| [-1,4] / [2,1] / [1] | 2 |
最小值为1。