1873E.md (2441B)
1 Source: https://codeforces.com/problemset/problem/1873/E 2 3 E. Building an Aquarium 4 5 time limit per test 6 7 2 seconds 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 You love fish, that's why you have decided to build an aquarium. You have a piece of coral made of $n$ columns, the $i$-th of which is $a_i$ units tall. Afterwards, you will build a tank around the coral as follows: 22 23 * Pick an integer $h \geq 1$ — the height of the tank. Build walls of height $h$ on either side of the tank. 24 * Then, fill the tank up with water so that the height of each column is $h$, unless the coral is taller than $h$; then no water should be added to this column. 25 26 For example, with $a=[3,1,2,4,6,2,5]$ and a height of $h=4$, you will end up using a total of $w=8$ units of water, as shown.  You can use at most $x$ units of water to fill up the tank, but you want to build the biggest tank possible. What is the largest value of $h$ you can select? 27 28 Input 29 30 The first line contains a single integer $t$ ($1 \leq t \leq 10^4$) — the number of test cases. 31 32 The first line of each test case contains two positive integers $n$ and $x$ ($1 \leq n \leq 2 \cdot 10^5$; $1 \leq x \leq 10^9$) — the number of columns of the coral and the maximum amount of water you can use. 33 34 The second line of each test case contains $n$ space-separated integers $a_i$ ($1 \leq a_i \leq 10^9$) — the heights of the coral. 35 36 The sum of $n$ over all test cases doesn't exceed $2 \cdot 10^5$. 37 38 Output 39 40 For each test case, output a single positive integer $h$ ($h \geq 1$) — the maximum height the tank can have, so you need at most $x$ units of water to fill up the tank. 41 42 We have a proof that under these constraints, such a value of $h$ always exists. 43 44 Example 45 46 Input 47 48 ``` 49 5 50 51 7 9 52 53 3 1 2 4 6 2 5 54 55 3 10 56 57 1 1 1 58 59 4 1 60 61 1 4 3 4 62 63 6 1984 64 65 2 6 5 9 1 8 66 67 1 1000000000 68 69 1 70 ``` 71 72 Output 73 74 ``` 75 4 76 4 77 2 78 335 79 1000000001 80 ``` 81 82 Note 83 84 The first test case is pictured in the statement. With $h=4$ we need $8$ units of water, but if $h$ is increased to $5$ we need $13$ units of water, which is more than $x=9$. So $h=4$ is optimal. 85 86 In the second test case, we can pick $h=4$ and add $3$ units to each column, using a total of $9$ units of water. It can be shown that this is optimal. 87 88 In the third test case, we can pick $h=2$ and use all of our water, so it is optimal.