2170B.md (2197B)
1 Source: https://codeforces.com/problemset/problem/2170/B 2 3 B. Addition on a Segment 4 5 time limit per test 6 7 2 seconds 8 9 memory limit per test 10 11 512 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 You start with an integer array $a$, which initially consists of $n$ zeros. You have to perform the following action exactly $n$ times: 22 23 * choose two integers $l$ and $r$ ($1 \le l \le r \le n$) and assign $a_{i} = a_{i} + 1$ for each $i$ such that $l \le i \le r$. 24 25 You are given an array $b$, consisting of $n$ integers. Your task is to choose such values $l$ and $r$ for each action that: 26 27 * after all $n$ actions are performed, it's possible to reorder the elements in such a way that $a$ becomes equal to $b$; 28 * the maximum value of $r - l + 1$ over all actions is as large as possible. 29 30 What's the maximum possible value of $r - l + 1$? 31 32 Input 33 34 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. 35 36 The first line of each test case contains one integer $n$ ($1 \le n \le 2 \cdot 10^{5}$) — the length of the array $b$. 37 38 The second line of each test case contains $n$ integers $b_{i}$ ($0 \le b_{i} \le n$) — the elements of the array $b$. 39 40 Additional constraints on the input: 41 42 * there exists at least one way to choose $l$ and $r$ for each action and reorder the elements at the end so that $a$ becomes equal to $b$; 43 * the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$. 44 45 Output 46 47 For each test case, output one integer — the answer to the problem. 48 49 Example 50 51 Input 52 53 ``` 54 3 55 56 5 57 58 0 5 1 0 1 59 60 3 61 62 3 2 1 63 64 5 65 66 1 1 1 1 1 67 ``` 68 69 Output 70 71 ``` 72 3 73 74 3 75 76 1 77 ``` 78 79 Note 80 81 Consider the first test case. If the $n$ actions were as follows: 82 83 * $l = 3$ and $r = 3$ 84 * $l = 1$ and $r = 3$ 85 * $l = 3$ and $r = 3$ 86 * $l = 3$ and $r = 3$ 87 * $l = 3$ and $r = 3$ 88 89 The array $a = [1, 1, 5, 0, 0]$, so you can reorder the elements to make it equal to $[0, 5, 1, 0, 1]$. As can be seen in this case, the maximum value of $r - l + 1$ is $3$. It can be shown that this is the optimal answer. 90 91 In the second test case: 92 93 * $l = 1$ and $r = 3$ 94 * $l = 2$ and $r = 3$ 95 * $l = 3$ and $r = 3$ 96 97 The answer is $3$.