Codeforces Round 898 (Div. 4) E. Building an Aquarium
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 \(ai\) units tall. Afterwards, you will build a tank around the coral as follows:
- Pick an integer \(h≥1\) — the height of the tank. Build walls of height \(ℎ\) on either side of the tank.
- 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.
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?
Input
The first line contains a single integer \(t\) (\(1 \leq t \leq 10^4\)) — the number of test cases.
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.
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.
The sum of \(n\) over all test cases doesn't exceed \(2 \cdot 10^5\).
Output
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.
We have a proof that under these constraints, such a value of \(h\) always exists.
- Example
Input
5
7 9
3 1 2 4 6 2 5
3 10
1 1 1
4 1
1 4 3 4
6 1984
2 6 5 9 1 8
1 1000000000
1
Output
4
4
2
335
1000000001
思路分析：二分答案标准模版，从0-2e9依次枚举x，直到找到合适的h。使用二分是将左右边界尽量开大，在logn的时间复杂度下，这个数据并不是很大。
#include<iostream>
using namespace std;
//#define int long long
const int N = 2e5 + 20;
int a[N], n,x;
int t;
bool check(int h) {
int s = 0;
for (int i = 0; i < n; i++)
if (h > a[i]) {
s = s + (h - a[i]);
if (s > x) return false;
}
return true;
}
int main() {
cin.tie(0);
cout.tie(0);
cin >> t;
while (t--) {
cin >> n >> x;
for (int i = 0; i < n; i++) cin >> a[i];
int l = 0, r = 1e9+500;
while (l < r) {
int mid = (l + r + 1) / 2;
if (check(mid)) l=mid; //如果mid符合更新l，继续找
else r=mid-1;
}
cout << l << endl;
}
return 0;
}