---
# System prepended metadata

title: E. Building an Aquarium
tags: [codeforce meadium_low(1100~1600), binary search]

---

link：https://codeforces.com/problemset/problem/1873/E

* 首先，先設定最大上限 **max_limit** 為 $x+v[i]，i=1\sim n$
* 接著，用二分搜在 **1~max_limit** 中搜尋高度，並找到不大於 $x$ 個剩餘空格的高度 $h$ (利用右側邊界的二分搜)
```C++=

#include <bits/stdc++.h>
using namespace std;

int t;
int n,x;

long long int count_blank(int inp, vector<int> &v){
    long long int ans = 0;
    for(int i=0;i<v.size();i++){
        ans+=(inp-v[i])*(v[i]<=inp);
    }
    return ans;
}

long long int upper_bounds(long long int &max_limit, vector<int> &v){
    long long int start = 1;
    long long int ends = max_limit;
    long long int count;

    while(start <= ends){
        long long int mid = start + (ends-start)/2;
        count = count_blank(mid,v);
        if (count>x) ends = mid-1;
        else start = mid+1;

    }
    return ends;
}

int main()
{
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    
    cin>>t;
    while(t--){
        cin>>n>>x;
        vector<int> v(n);
        long long int sum = 0;
        for (int i=0;i<n;i++){
            cin>>v[i];
            sum+=v[i];
        }
        long long int max_limit = (sum+x)/n;
        long long int ans= upper_bounds(max_limit, v);
        cout<<ans<<"\n";
    }
}
```