C. Building an Aquarium题解

unicornshjl · 2024-11-27 09:06:18 · 个人记录

Problem C.Building an Aquarium题解

#

简化题意

给定 n 个高度和最多可以注水的数量 x。对一个给定的 h,需要的注水量为：对所有的 i，如果 a_i 的高度比 h 低，那么当前的 i 对注水量的贡献为 h-a_i。你需要求出最大的 h 使得其注水量不超过给定的 x。

分析：经典的锯木头问题，二分题的模板。对于一个给定的 h,\operatorname{check} 函数中我们只需要求出下式的值,按照以下方式判断 sum 与给定的 x 的关系：

• 若 sum≤x 则 return true。
• 否则 return false 。

其中，sum 的定义如下：

关于右边界大小，当 n=1,x=10^9,a_1=10^9 时，右边界 r 最大为 2\times10^9。可以发现，没有其他的情况会使右边界比 2\times10^9 更大了。 # 代码如下

#include<bits/stdc++.h>
#define int long long 
using namespace std;
const int N=2e5+10;
int a[N],n,m;
bool check(int x){
    int sum=0;
    for(int i=1;i<=n;i++)
        sum+=max(x-a[i],0ll);
//注意0ll,sum可能超过int范围所以使用long long,此时0应该改为0ll否则会WA
    return sum<=m;
}
signed main(){
    ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
    int T;cin>>T;
    while(T--){
        cin>>n>>m;
        for(int i=1;i<=n;i++)
            cin>>a[i];
        int l=0,r=2e9;
    //右边界的最大值为1e9+1e9=2e9
        int ans=0;//用ans记录答案
        while(l<=r){
            int mid=(l+r)>>1;
            if(check(mid)){
                ans=mid;
                l=mid+1;
            }
            else 
                r=mid-1;
        }
        cout<<ans<<"\n";
    }
    return 0;
}