E. Building an Aquarium

题目描述

本题其实思想就是找对一个点,使得这个高度的时候水不超过给的值,这个点再多一下下,就会超出给的值,所以我们可以采用二分,但要注意的是,因为要找的点一定不能过大,所以我们使用l+r>>1

#include<iostream>
#include<algorithm>
#include<map>
typedef long long L;
using namespace std;
const int N = 200050; 
L arr[N];
L n,m,mmin,T;
int main()
{
    cin >> T;
    while (T--) {
       
        L sum = 0, ans = 0;
        cin >> n >> m;
        for (int i = 0; i < n; i++)
            cin >> arr[i];
        L l = 0, r = 1e10;//采用二分
        while (l < r)
        {
            L mid = l + r >> 1;
            sum = 0;
            for (int i = 0; i < n; i++) {
                if (mid >= arr[i]) sum += (mid - arr[i]);
                //高度一定是要高于砖块才可以
            }
            if (sum<=m) l = mid + 1, ans = mid;//记录答案
            else r = mid;

        }
        cout << ans<<endl;
    }
        return 0;
}