A15369. Rebellion
编程题
普及/提高-
知识点
题目描述
You have an array $a$ of size $n$ consisting only of zeroes and ones. You can do the following operation:
- choose two indices $1 \le i , j \le n$ , $i \ne j$ ,
- add $a_{i}$ to $a_{j}$ ,
- remove $a_{i}$ from $a$ .
Note that elements of $a$ can become bigger than $1$ after performing some operations. Also note that $n$ becomes $1$ less after the operation.
What is the minimum number of operations needed to make $a$ non-decreasing, i. e. that each element is not less than the previous element?
- choose two indices $1 \le i , j \le n$ , $i \ne j$ ,
- add $a_{i}$ to $a_{j}$ ,
- remove $a_{i}$ from $a$ .
Note that elements of $a$ can become bigger than $1$ after performing some operations. Also note that $n$ becomes $1$ less after the operation.
What is the minimum number of operations needed to make $a$ non-decreasing, i. e. that each element is not less than the previous element?
输入格式
Each test contains multiple test cases. The first line contains the number of test cases $t$ ( $1 \le t \le 10^4$ ). The description of the test cases follows.
The first line of each test case contains an integer $n$ ( $1 \le n \le 10^5$ ), the size of array $a$ .
Next line contains $n$ integers $a_{1}, a_{2}, \ldots a_{n}$ ( $a_i$ is $0$ or $1$ ), elements of array $a$ .
It's guaranteed that sum of $n$ over all test cases doesn't exceed $2 \cdot 10^5$ .
The first line of each test case contains an integer $n$ ( $1 \le n \le 10^5$ ), the size of array $a$ .
Next line contains $n$ integers $a_{1}, a_{2}, \ldots a_{n}$ ( $a_i$ is $0$ or $1$ ), elements of array $a$ .
It's guaranteed that sum of $n$ over all test cases doesn't exceed $2 \cdot 10^5$ .
输出格式
For each test case print a single integer, minimum number of operations needed to make $a$ non-decreasing.
输入输出样例
输入 #1
4 8 0 0 1 1 1 1 1 1 5 1 0 0 1 1 2 1 0 11 1 1 0 0 1 0 0 1 1 1 0
输出 #1
0 1 1 3
说明/提示
In the first test case, $a$ is already non-decreasing, so you don't need to do any operations and the answer is $0$ .
In the second test case, you can perform an operation for $i = 1$ and $j = 5$ , so $a$ will be equal to $[0, 0, 1, 2]$ and it becomes non-decreasing.
In the third test case, you can perform an operation for $i = 2$ and $j = 1$ , so $a$ will be equal to $[1]$ and it becomes non-decreasing.
In the second test case, you can perform an operation for $i = 1$ and $j = 5$ , so $a$ will be equal to $[0, 0, 1, 2]$ and it becomes non-decreasing.
In the third test case, you can perform an operation for $i = 2$ and $j = 1$ , so $a$ will be equal to $[1]$ and it becomes non-decreasing.