309783: CF1735B. Tea with Tangerines
Memory Limit：256 MB
Time Limit：1 S
Judge Style：Text Compare
Creator：
Submit：0
Solved：0
Description
Tea with Tangerines
题意翻译
有 $n$ 块橘子皮，每块大小是 $a[i]$。你可以做一次操作将一块橘子皮分成任意大小的两块，整个过程橘子皮总量是不变的。问要使任意两块橘子皮 $x,y\ (x\le y)$ 都满足 $2x>y$ 的最小操作数。题目描述
There are $ n $ pieces of tangerine peel, the $ i $ -th of them has size $ a_i $ . In one step it is possible to divide one piece of size $ x $ into two pieces of positive integer sizes $ y $ and $ z $ so that $ y + z = x $ . You want that for each pair of pieces, their sizes differ strictly less than twice. In other words, there should not be two pieces of size $ x $ and $ y $ , such that $ 2x \le y $ . What is the minimum possible number of steps needed to satisfy the condition?输入输出格式
输入格式
The first line of the input contains a single integer $ t $ ( $ 1 \le t \le 100 $ ) — the number of test cases. The description of test cases follows. The first line of each test case contains the integer $ n $ ( $ 1 \le n \le 100 $ ). Then one line follows, containing $ n $ integers $ a_1 \le a_2 \le \ldots \le a_n $ ( $ 1 \le a_i \le 10^7 $ ).
输出格式
For each test case, output a single line containing the minimum number of steps.
输入输出样例
输入样例 #1
3
5
1 2 3 4 5
1
1033
5
600 900 1300 2000 2550输出样例 #1
10
0
4说明
In the first test case, we initially have a piece of size $ 1 $ , so all final pieces must have size $ 1 $ . The total number of steps is: $ 0 + 1 + 2 + 3 + 4 = 10 $ . In the second test case, we have just one piece, so we don't need to do anything, and the answer is $ 0 $ steps. In the third test case, one of the possible cut options is: $ 600,\ 900,\ (600 | 700),\ (1000 | 1000),\ (1000 | 1000 | 550) $ . You can see this option in the picture below. The maximum piece has size $ 1000 $ , and it is less than $ 2 $ times bigger than the minimum piece of size $ 550 $ . $ 4 $ steps are done. We can show that it is the minimum possible number of steps. Input
题意翻译
有 $n$ 块橘子皮，每块大小是 $a[i]$。你可以做一次操作将一块橘子皮分成任意大小的两块，整个过程橘子皮总量是不变的。问要使任意两块橘子皮 $x,y\ (x\le y)$ 都满足 $2x>y$ 的最小操作数。Output
**题意翻译**
存在 $ n $ 块橘子皮，每块的大小为 $ a[i] $。你可以通过一次操作将一块大小为 $ x $ 的橘子皮分成两块任意正整数大小的块 $ y $ 和 $ z $，使得 $ y + z = x $。目标是要使得任意两块橘子皮 $ x, y $（$ x \le y $）都满足 $ 2x > y $。求满足条件的最小操作数。
**题目描述**
有 $ n $ 块橘子皮，第 $ i $ 块的大小为 $ a_i $。每一步可以将一块大小为 $ x $ 的橘子皮分成两块正整数大小的块 $ y $ 和 $ z $，使得 $ y + z = x $。你希望对于每一对橘子皮，它们的大小之差严格小于两倍。换句话说，不应该有两块大小为 $ x $ 和 $ y $ 的橘子皮，使得 $ 2x \le y $。求满足条件所需的最小步数。
**输入输出格式**
**输入格式**
输入的第一行包含一个整数 $ t $（$ 1 \le t \le 100 $）——测试用例的数量。接下来是每个测试用例的描述。
每个测试用例的第一行包含一个整数 $ n $（$ 1 \le n \le 100 $）。
然后是一行，包含 $ n $ 个整数 $ a_1 \le a_2 \le \ldots \le a_n $（$ 1 \le a_i \le 10^7 $）。
**输出格式**
对于每个测试用例，输出一行包含满足条件所需的最小步数。
**输入输出样例**
**输入样例 #1**
```
3
5
1 2 3 4 5
1
1033
5
600 900 1300 2000 2550
```
**输出样例 #1**
```
10
0
4
```
**说明**
在第一个测试用例中，最初有一块大小为 $ 1 $ 的橘子皮，所以所有的最终橘子皮块必须都有大小 $ 1 $。总步数为：$ 0 + 1 + 2 + 3 + 4 = 10 $。
在第二个测试用例中，我们只有一块橘子皮，所以不需要进行任何操作，答案为 $ 0 $ 步。
在第三个测试用例中，一种可能的切割选项是：$ 600, 900, (600 | 700), (1000 | 1000), (1000 | 1000 | 550) $。你可以从下图中看到这个选项。最大的块大小为 $ 1000 $，它不到最小块大小 $ 550 $ 的两倍大。进行了 $ 4 $ 步。我们可以证明这是可能的最小步数。**题意翻译** 存在 $ n $ 块橘子皮，每块的大小为 $ a[i] $。你可以通过一次操作将一块大小为 $ x $ 的橘子皮分成两块任意正整数大小的块 $ y $ 和 $ z $，使得 $ y + z = x $。目标是要使得任意两块橘子皮 $ x, y $（$ x \le y $）都满足 $ 2x > y $。求满足条件的最小操作数。 **题目描述** 有 $ n $ 块橘子皮，第 $ i $ 块的大小为 $ a_i $。每一步可以将一块大小为 $ x $ 的橘子皮分成两块正整数大小的块 $ y $ 和 $ z $，使得 $ y + z = x $。你希望对于每一对橘子皮，它们的大小之差严格小于两倍。换句话说，不应该有两块大小为 $ x $ 和 $ y $ 的橘子皮，使得 $ 2x \le y $。求满足条件所需的最小步数。 **输入输出格式** **输入格式** 输入的第一行包含一个整数 $ t $（$ 1 \le t \le 100 $）——测试用例的数量。接下来是每个测试用例的描述。 每个测试用例的第一行包含一个整数 $ n $（$ 1 \le n \le 100 $）。 然后是一行，包含 $ n $ 个整数 $ a_1 \le a_2 \le \ldots \le a_n $（$ 1 \le a_i \le 10^7 $）。 **输出格式** 对于每个测试用例，输出一行包含满足条件所需的最小步数。 **输入输出样例** **输入样例 #1** ``` 3 5 1 2 3 4 5 1 1033 5 600 900 1300 2000 2550 ``` **输出样例 #1** ``` 10 0 4 ``` **说明** 在第一个测试用例中，最初有一块大小为 $ 1 $ 的橘子皮，所以所有的最终橘子皮块必须都有大小 $ 1 $。总步数为：$ 0 + 1 + 2 + 3 + 4 = 10 $。 在第二个测试用例中，我们只有一块橘子皮，所以不需要进行任何操作，答案为 $ 0 $ 步。 在第三个测试用例中，一种可能的切割选项是：$ 600, 900, (600 | 700), (1000 | 1000), (1000 | 1000 | 550) $。你可以从下图中看到这个选项。最大的块大小为 $ 1000 $，它不到最小块大小 $ 550 $ 的两倍大。进行了 $ 4 $ 步。我们可以证明这是可能的最小步数。
存在 $ n $ 块橘子皮，每块的大小为 $ a[i] $。你可以通过一次操作将一块大小为 $ x $ 的橘子皮分成两块任意正整数大小的块 $ y $ 和 $ z $，使得 $ y + z = x $。目标是要使得任意两块橘子皮 $ x, y $（$ x \le y $）都满足 $ 2x > y $。求满足条件的最小操作数。
**题目描述**
有 $ n $ 块橘子皮，第 $ i $ 块的大小为 $ a_i $。每一步可以将一块大小为 $ x $ 的橘子皮分成两块正整数大小的块 $ y $ 和 $ z $，使得 $ y + z = x $。你希望对于每一对橘子皮，它们的大小之差严格小于两倍。换句话说，不应该有两块大小为 $ x $ 和 $ y $ 的橘子皮，使得 $ 2x \le y $。求满足条件所需的最小步数。
**输入输出格式**
**输入格式**
输入的第一行包含一个整数 $ t $（$ 1 \le t \le 100 $）——测试用例的数量。接下来是每个测试用例的描述。
每个测试用例的第一行包含一个整数 $ n $（$ 1 \le n \le 100 $）。
然后是一行，包含 $ n $ 个整数 $ a_1 \le a_2 \le \ldots \le a_n $（$ 1 \le a_i \le 10^7 $）。
**输出格式**
对于每个测试用例，输出一行包含满足条件所需的最小步数。
**输入输出样例**
**输入样例 #1**
```
3
5
1 2 3 4 5
1
1033
5
600 900 1300 2000 2550
```
**输出样例 #1**
```
10
0
4
```
**说明**
在第一个测试用例中，最初有一块大小为 $ 1 $ 的橘子皮，所以所有的最终橘子皮块必须都有大小 $ 1 $。总步数为：$ 0 + 1 + 2 + 3 + 4 = 10 $。
在第二个测试用例中，我们只有一块橘子皮，所以不需要进行任何操作，答案为 $ 0 $ 步。
在第三个测试用例中，一种可能的切割选项是：$ 600, 900, (600 | 700), (1000 | 1000), (1000 | 1000 | 550) $。你可以从下图中看到这个选项。最大的块大小为 $ 1000 $，它不到最小块大小 $ 550 $ 的两倍大。进行了 $ 4 $ 步。我们可以证明这是可能的最小步数。**题意翻译** 存在 $ n $ 块橘子皮，每块的大小为 $ a[i] $。你可以通过一次操作将一块大小为 $ x $ 的橘子皮分成两块任意正整数大小的块 $ y $ 和 $ z $，使得 $ y + z = x $。目标是要使得任意两块橘子皮 $ x, y $（$ x \le y $）都满足 $ 2x > y $。求满足条件的最小操作数。 **题目描述** 有 $ n $ 块橘子皮，第 $ i $ 块的大小为 $ a_i $。每一步可以将一块大小为 $ x $ 的橘子皮分成两块正整数大小的块 $ y $ 和 $ z $，使得 $ y + z = x $。你希望对于每一对橘子皮，它们的大小之差严格小于两倍。换句话说，不应该有两块大小为 $ x $ 和 $ y $ 的橘子皮，使得 $ 2x \le y $。求满足条件所需的最小步数。 **输入输出格式** **输入格式** 输入的第一行包含一个整数 $ t $（$ 1 \le t \le 100 $）——测试用例的数量。接下来是每个测试用例的描述。 每个测试用例的第一行包含一个整数 $ n $（$ 1 \le n \le 100 $）。 然后是一行，包含 $ n $ 个整数 $ a_1 \le a_2 \le \ldots \le a_n $（$ 1 \le a_i \le 10^7 $）。 **输出格式** 对于每个测试用例，输出一行包含满足条件所需的最小步数。 **输入输出样例** **输入样例 #1** ``` 3 5 1 2 3 4 5 1 1033 5 600 900 1300 2000 2550 ``` **输出样例 #1** ``` 10 0 4 ``` **说明** 在第一个测试用例中，最初有一块大小为 $ 1 $ 的橘子皮，所以所有的最终橘子皮块必须都有大小 $ 1 $。总步数为：$ 0 + 1 + 2 + 3 + 4 = 10 $。 在第二个测试用例中，我们只有一块橘子皮，所以不需要进行任何操作，答案为 $ 0 $ 步。 在第三个测试用例中，一种可能的切割选项是：$ 600, 900, (600 | 700), (1000 | 1000), (1000 | 1000 | 550) $。你可以从下图中看到这个选项。最大的块大小为 $ 1000 $，它不到最小块大小 $ 550 $ 的两倍大。进行了 $ 4 $ 步。我们可以证明这是可能的最小步数。