问题 6276 --最大得分

6276: 最大得分★★★

时间限制: 1 Sec  内存限制: 128 MB
提交: 14  解决: 1
[提交][状态][命题人:]

题目描述

明明同学有n块金属，编号从1到n，第i块金属的重量为ai。

同时，明明同学有3个从1到3编号的袋子，袋子最初是空的。明明同学需要将所有的金属都装到袋子里，确保每块金属都被装到袋子里，每个袋子里至少有一块金属（三个袋子都不能为空）。

在明明同学将n块金属全部装进袋子后，洋洋同学将从每个袋子中取出一块金属，共3块金属。设wj为洋洋同学从袋子j中取出的金属的重量。规定洋洋同学的得分为：|w1−w2|+|w2−w3|，其中|x|表示x的绝对值。

众所周知，洋洋同学会以一种使分数最小化的方式选取金属（即希望得分尽量小）。如果明明同学按照最优方式将所有金属装入三个袋子中（明明同学希望洋洋同学的得分尽量大），洋洋同学最终的得分最大是多少?

输入

       第一行一个整数t（1≤t≤2e4）：测试样例数；

        每个测试样例两行：

第一行一个整数n（3<=n <=2e5）：金属块的数量。

第二行n个整数：a1,a2,……,an(1<=ai<=1e9): n块金属的重量；

        测试数据确保，所有测试用例的n之和不超过2e5.

输出

对于每个测试样例，输出一个一个整数：明明同学按照最优方式将n块金属装入3个袋子后，洋洋同学的最小得分值。

样例输入
Copy
3
5
3 1 5 2 3
4
17 8 19 45
8
265 265 265 265 265 265 265 265
样例输出
Copy
6
63
0

提示

      对于第一个测试样例，明明同学将编号为1，4，5这三块金属装入第一个袋子，编号为3的金属装入第二个袋子，编号为2的金属装入第三个袋子，此时三个袋子中的金属重量分别为：{3,2,3},{5},{1}，此时洋洋只能从第一个袋子选择重量为3的金属，第二个袋子选择重量为5的金属，第三个袋子中选择重量为1的金属，此时洋洋的最小得分为|3-5|+|5-1|=6。对于明明同学而言，再也找不到其他分配金属的方法，使得洋洋同学的得分更高了。

来源

ZXS2023 

[提交][状态]