309817: CF1740C. Bricks and Bags
Memory Limit：256 MB
Time Limit：1 S
Judge Style：Text Compare
Creator：
Submit：0
Solved：0
Description
Bricks and Bags
题意翻译
hhoppitree 有 $n$ 根木棍，其中第 $i$ 根木棍的长度为 $a_i$，他想要将它们放置在三个背包中，使得**每个背包中至少有一根木棍**。 他的好朋友会从每个背包中选出一根木棍，假设从三个背包中取出的木棍的长度分别为 $x,y,z$，则他会送给 hhoppitree 一共 $|x-y|+|y-z|$ 瓶可乐，显然，**他的朋友会最小化这个数的值**。 hhoppitree 想通过适当的分配，使得这个数的最小可能值最大，他想知道这个最大值是多少。题目描述
There are $ n $ bricks numbered from $ 1 $ to $ n $ . Brick $ i $ has a weight of $ a_i $ . Pak Chanek has $ 3 $ bags numbered from $ 1 $ to $ 3 $ that are initially empty. For each brick, Pak Chanek must put it into one of the bags. After this, each bag must contain at least one brick. After Pak Chanek distributes the bricks, Bu Dengklek will take exactly one brick from each bag. Let $ w_j $ be the weight of the brick Bu Dengklek takes from bag $ j $ . The score is calculated as $ |w_1 - w_2| + |w_2 - w_3| $ , where $ |x| $ denotes the absolute value of $ x $ . It is known that Bu Dengklek will take the bricks in such a way that minimises the score. What is the maximum possible final score if Pak Chanek distributes the bricks optimally?输入输出格式
输入格式
Each test contains multiple test cases. The first line contains an integer $ t $ ( $ 1 \leq t \leq 2 \cdot 10^4 $ ) — the number of test cases. The following lines contain the description of each test case. The first line of each test case contains an integer $ n $ ( $ 3 \leq n \leq 2 \cdot 10^5 $ ) — the number of bricks. The second line of each test case contains $ n $ integers $ a_1, a_2, \ldots, a_n $ ( $ 1 \leq a_i \leq 10^9 $ ) — the weights of the bricks. It is guaranteed that the sum of $ n $ over all test cases does not exceed $ 2 \cdot 10^5 $ .
输出格式
For each test case, output a line containing an integer representing the maximum possible final score if Pak Chanek distributes the bricks optimally.
输入输出样例
输入样例 #1
3
5
3 1 5 2 3
4
17 8 19 45
8
265 265 265 265 265 265 265 265输出样例 #1
6
63
0说明
In the first test case, one way of achieving a final score of $ 6 $ is to do the following: - Put bricks $ 1 $ , $ 4 $ , and $ 5 $ into bag $ 1 $ . - Put brick $ 3 $ into bag $ 2 $ . - Put brick $ 2 $ into bag $ 3 $ . If Pak Chanek distributes the bricks that way, a way Bu Dengklek can take the bricks is: - Take brick $ 5 $ from bag $ 1 $ . - Take brick $ 3 $ from bag $ 2 $ . - Take brick $ 2 $ from bag $ 3 $ . The score is $ |a_5 - a_3| + |a_3 - a_2| = |3 - 5| + |5 - 1| = 6 $ . It can be shown that Bu Dengklek cannot get a smaller score from this distribution. It can be shown that there is no other distribution that results in a final score bigger than $ 6 $ .Input
题意翻译
hhoppitree 有 $n$ 根木棍，其中第 $i$ 根木棍的长度为 $a_i$，他想要将它们放置在三个背包中，使得**每个背包中至少有一根木棍**。 他的好朋友会从每个背包中选出一根木棍，假设从三个背包中取出的木棍的长度分别为 $x,y,z$，则他会送给 hhoppitree 一共 $|x-y|+|y-z|$ 瓶可乐，显然，**他的朋友会最小化这个数的值**。 hhoppitree 想通过适当的分配，使得这个数的最小可能值最大，他想知道这个最大值是多少。Output
**题意翻译**
hhoppitree 有 $n$ 根木棍，其中第 $i$ 根木棍的长度为 $a_i$，他想要将它们放置在三个背包中，使得**每个背包中至少有一根木棍**。
他的好朋友会从每个背包中选出一根木棍，假设从三个背包中取出的木棍的长度分别为 $x,y,z$，则他会送给 hhoppitree 一共 $|x-y|+|y-z|$ 瓶可乐，显然，**他的朋友会最小化这个数的值**。
hhoppitree 想通过适当的分配，使得这个数的最小可能值最大，他想知道这个最大值是多少。
**题目描述**
There are $ n $ bricks numbered from $ 1 $ to $ n $. Brick $ i $ has a weight of $ a_i $.
Pak Chanek has $ 3 $ bags numbered from $ 1 $ to $ 3 $ that are initially empty. For each brick, Pak Chanek must put it into one of the bags. After this, each bag must contain at least one brick.
After Pak Chanek distributes the bricks, Bu Dengklek will take exactly one brick from each bag. Let $ w_j $ be the weight of the brick Bu Dengklek takes from bag $ j $. The score is calculated as $ |w_1 - w_2| + |w_2 - w_3| $, where $ |x| $ denotes the absolute value of $ x $.
It is known that Bu Dengklek will take the bricks in such a way that minimises the score. What is the maximum possible final score if Pak Chanek distributes the bricks optimally?
**输入输出格式**
**输入格式**
每个测试包含多个测试用例。第一行包含一个整数 $ t $ ( $ 1 \leq t \leq 2 \cdot 10^4 $ ) — 测试用例的数量。接下来的行包含每个测试用例的描述。
每个测试用例的第一行包含一个整数 $ n $ ( $ 3 \leq n \leq 2 \cdot 10^5 $ ) — 砖块的数量。
每个测试用例的第二行包含 $ n $ 个整数 $ a_1, a_2, \ldots, a_n $ ( $ 1 \leq a_i \leq 10^9 $ ) — 砖块的重量。
保证所有测试用例的 $ n $ 之和不超过 $ 2 \cdot 10^5 $。
**输出格式**
对于每个测试用例，输出一个整数，表示如果 Pak Chanek 优化地分配砖块，可能得到的最大最终得分。
**输入输出样例**
**输入样例 #1**
```
3
5
3 1 5 2 3
4
17 8 19 45
8
265 265 265 265 265 265 265 265
```
**输出样例 #1**
```
6
63
0
```
**说明**
在第一个测试用例中，一种得到最终得分 $ 6 $ 的方法是：
- 将砖块 $ 1 $, $ 4 $, 和 $ 5 $ 放入包 $ 1 $。
- 将砖块 $ 3 $ 放入包 $ 2 $。
- 将砖块 $ 2 $ 放入包 $ 3 $。
如果 Pak Chanek 这样分配砖块，Bu Dengklek 可以这样取砖块：
- 从包 $ 1 $ 取砖块 $ 5 $。
- 从包 $ 2 $ 取砖块 $ 3 $。
- 从包 $ 3 $ 取砖块 $ 2 $。
得分为 $ |a_5 - a_3| + |a_3 - a_2| = |3 - 5| + |5 - 1| = 6 $。可以证明 Bu Dengklek 无法从这个分配中得到更小的得分。
可以证明没有其他分配会导致比 $ 6 $ 更大的最终得分。**题意翻译** hhoppitree 有 $n$ 根木棍，其中第 $i$ 根木棍的长度为 $a_i$，他想要将它们放置在三个背包中，使得**每个背包中至少有一根木棍**。 他的好朋友会从每个背包中选出一根木棍，假设从三个背包中取出的木棍的长度分别为 $x,y,z$，则他会送给 hhoppitree 一共 $|x-y|+|y-z|$ 瓶可乐，显然，**他的朋友会最小化这个数的值**。 hhoppitree 想通过适当的分配，使得这个数的最小可能值最大，他想知道这个最大值是多少。 **题目描述** There are $ n $ bricks numbered from $ 1 $ to $ n $. Brick $ i $ has a weight of $ a_i $. Pak Chanek has $ 3 $ bags numbered from $ 1 $ to $ 3 $ that are initially empty. For each brick, Pak Chanek must put it into one of the bags. After this, each bag must contain at least one brick. After Pak Chanek distributes the bricks, Bu Dengklek will take exactly one brick from each bag. Let $ w_j $ be the weight of the brick Bu Dengklek takes from bag $ j $. The score is calculated as $ |w_1 - w_2| + |w_2 - w_3| $, where $ |x| $ denotes the absolute value of $ x $. It is known that Bu Dengklek will take the bricks in such a way that minimises the score. What is the maximum possible final score if Pak Chanek distributes the bricks optimally? **输入输出格式** **输入格式** 每个测试包含多个测试用例。第一行包含一个整数 $ t $ ( $ 1 \leq t \leq 2 \cdot 10^4 $ ) — 测试用例的数量。接下来的行包含每个测试用例的描述。 每个测试用例的第一行包含一个整数 $ n $ ( $ 3 \leq n \leq 2 \cdot 10^5 $ ) — 砖块的数量。 每个测试用例的第二行包含 $ n $ 个整数 $ a_1, a_2, \ldots, a_n $ ( $ 1 \leq a_i \leq 10^9 $ ) — 砖块的重量。 保证所有测试用例的 $ n $ 之和不超过 $ 2 \cdot 10^5 $。 **输出格式** 对于每个测试用例，输出一个整数，表示如果 Pak Chanek 优化地分配砖块，可能得到的最大最终得分。 **输入输出样例** **输入样例 #1** ``` 3 5 3 1 5 2 3 4 17 8 19 45 8 265 265 265 265 265 265 265 265 ``` **输出样例 #1** ``` 6 63 0 ``` **说明** 在第一个测试用例中，一种得到最终得分 $ 6 $ 的方法是： - 将砖块 $ 1 $, $ 4 $, 和 $ 5 $ 放入包 $ 1 $。 - 将砖块 $ 3 $ 放入包 $ 2 $。 - 将砖块 $ 2 $ 放入包 $ 3 $。 如果 Pak Chanek 这样分配砖块，Bu Dengklek 可以这样取砖块： - 从包 $ 1 $ 取砖块 $ 5 $。 - 从包 $ 2 $ 取砖块 $ 3 $。 - 从包 $ 3 $ 取砖块 $ 2 $。 得分为 $ |a_5 - a_3| + |a_3 - a_2| = |3 - 5| + |5 - 1| = 6 $。可以证明 Bu Dengklek 无法从这个分配中得到更小的得分。 可以证明没有其他分配会导致比 $ 6 $ 更大的最终得分。
hhoppitree 有 $n$ 根木棍，其中第 $i$ 根木棍的长度为 $a_i$，他想要将它们放置在三个背包中，使得**每个背包中至少有一根木棍**。
他的好朋友会从每个背包中选出一根木棍，假设从三个背包中取出的木棍的长度分别为 $x,y,z$，则他会送给 hhoppitree 一共 $|x-y|+|y-z|$ 瓶可乐，显然，**他的朋友会最小化这个数的值**。
hhoppitree 想通过适当的分配，使得这个数的最小可能值最大，他想知道这个最大值是多少。
**题目描述**
There are $ n $ bricks numbered from $ 1 $ to $ n $. Brick $ i $ has a weight of $ a_i $.
Pak Chanek has $ 3 $ bags numbered from $ 1 $ to $ 3 $ that are initially empty. For each brick, Pak Chanek must put it into one of the bags. After this, each bag must contain at least one brick.
After Pak Chanek distributes the bricks, Bu Dengklek will take exactly one brick from each bag. Let $ w_j $ be the weight of the brick Bu Dengklek takes from bag $ j $. The score is calculated as $ |w_1 - w_2| + |w_2 - w_3| $, where $ |x| $ denotes the absolute value of $ x $.
It is known that Bu Dengklek will take the bricks in such a way that minimises the score. What is the maximum possible final score if Pak Chanek distributes the bricks optimally?
**输入输出格式**
**输入格式**
每个测试包含多个测试用例。第一行包含一个整数 $ t $ ( $ 1 \leq t \leq 2 \cdot 10^4 $ ) — 测试用例的数量。接下来的行包含每个测试用例的描述。
每个测试用例的第一行包含一个整数 $ n $ ( $ 3 \leq n \leq 2 \cdot 10^5 $ ) — 砖块的数量。
每个测试用例的第二行包含 $ n $ 个整数 $ a_1, a_2, \ldots, a_n $ ( $ 1 \leq a_i \leq 10^9 $ ) — 砖块的重量。
保证所有测试用例的 $ n $ 之和不超过 $ 2 \cdot 10^5 $。
**输出格式**
对于每个测试用例，输出一个整数，表示如果 Pak Chanek 优化地分配砖块，可能得到的最大最终得分。
**输入输出样例**
**输入样例 #1**
```
3
5
3 1 5 2 3
4
17 8 19 45
8
265 265 265 265 265 265 265 265
```
**输出样例 #1**
```
6
63
0
```
**说明**
在第一个测试用例中，一种得到最终得分 $ 6 $ 的方法是：
- 将砖块 $ 1 $, $ 4 $, 和 $ 5 $ 放入包 $ 1 $。
- 将砖块 $ 3 $ 放入包 $ 2 $。
- 将砖块 $ 2 $ 放入包 $ 3 $。
如果 Pak Chanek 这样分配砖块，Bu Dengklek 可以这样取砖块：
- 从包 $ 1 $ 取砖块 $ 5 $。
- 从包 $ 2 $ 取砖块 $ 3 $。
- 从包 $ 3 $ 取砖块 $ 2 $。
得分为 $ |a_5 - a_3| + |a_3 - a_2| = |3 - 5| + |5 - 1| = 6 $。可以证明 Bu Dengklek 无法从这个分配中得到更小的得分。
可以证明没有其他分配会导致比 $ 6 $ 更大的最终得分。**题意翻译** hhoppitree 有 $n$ 根木棍，其中第 $i$ 根木棍的长度为 $a_i$，他想要将它们放置在三个背包中，使得**每个背包中至少有一根木棍**。 他的好朋友会从每个背包中选出一根木棍，假设从三个背包中取出的木棍的长度分别为 $x,y,z$，则他会送给 hhoppitree 一共 $|x-y|+|y-z|$ 瓶可乐，显然，**他的朋友会最小化这个数的值**。 hhoppitree 想通过适当的分配，使得这个数的最小可能值最大，他想知道这个最大值是多少。 **题目描述** There are $ n $ bricks numbered from $ 1 $ to $ n $. Brick $ i $ has a weight of $ a_i $. Pak Chanek has $ 3 $ bags numbered from $ 1 $ to $ 3 $ that are initially empty. For each brick, Pak Chanek must put it into one of the bags. After this, each bag must contain at least one brick. After Pak Chanek distributes the bricks, Bu Dengklek will take exactly one brick from each bag. Let $ w_j $ be the weight of the brick Bu Dengklek takes from bag $ j $. The score is calculated as $ |w_1 - w_2| + |w_2 - w_3| $, where $ |x| $ denotes the absolute value of $ x $. It is known that Bu Dengklek will take the bricks in such a way that minimises the score. What is the maximum possible final score if Pak Chanek distributes the bricks optimally? **输入输出格式** **输入格式** 每个测试包含多个测试用例。第一行包含一个整数 $ t $ ( $ 1 \leq t \leq 2 \cdot 10^4 $ ) — 测试用例的数量。接下来的行包含每个测试用例的描述。 每个测试用例的第一行包含一个整数 $ n $ ( $ 3 \leq n \leq 2 \cdot 10^5 $ ) — 砖块的数量。 每个测试用例的第二行包含 $ n $ 个整数 $ a_1, a_2, \ldots, a_n $ ( $ 1 \leq a_i \leq 10^9 $ ) — 砖块的重量。 保证所有测试用例的 $ n $ 之和不超过 $ 2 \cdot 10^5 $。 **输出格式** 对于每个测试用例，输出一个整数，表示如果 Pak Chanek 优化地分配砖块，可能得到的最大最终得分。 **输入输出样例** **输入样例 #1** ``` 3 5 3 1 5 2 3 4 17 8 19 45 8 265 265 265 265 265 265 265 265 ``` **输出样例 #1** ``` 6 63 0 ``` **说明** 在第一个测试用例中，一种得到最终得分 $ 6 $ 的方法是： - 将砖块 $ 1 $, $ 4 $, 和 $ 5 $ 放入包 $ 1 $。 - 将砖块 $ 3 $ 放入包 $ 2 $。 - 将砖块 $ 2 $ 放入包 $ 3 $。 如果 Pak Chanek 这样分配砖块，Bu Dengklek 可以这样取砖块： - 从包 $ 1 $ 取砖块 $ 5 $。 - 从包 $ 2 $ 取砖块 $ 3 $。 - 从包 $ 3 $ 取砖块 $ 2 $。 得分为 $ |a_5 - a_3| + |a_3 - a_2| = |3 - 5| + |5 - 1| = 6 $。可以证明 Bu Dengklek 无法从这个分配中得到更小的得分。 可以证明没有其他分配会导致比 $ 6 $ 更大的最终得分。