专栏文章

C. Building an Aquarium题解

uunicornshjl
个人记录参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@miqz9m1m
此快照首次捕获于
2025/12/04 13:10
3 个月前
此快照最后确认于
2025/12/04 13:10
3 个月前
查看原文

Problem C.Building an Aquarium题解

简化题意

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

分析：经典的锯木头问题，二分题的模板。对于一个给定的 hh,check⁡\operatorname{check} 函数中我们只需要求出下式的值,按照以下方式判断 sumsum 与给定的 xx 的关系：
  • 若 sum≤xsum≤x 则 return true。
  • 否则 return false 。
其中，sumsum 的定义如下：
sum=∑i=1nmax⁡(h−ai,0) sum=\sum_{i = 1}^{n} \max(h-a_i,0)
关于右边界大小，当 n=1,x=109,a1=109n=1,x=10^9,a_1=10^9 时，右边界 rr 最大为 2×1092\times10^9。可以发现，没有其他的情况会使右边界比 2×1092\times10^9 更大了。

代码如下
CPP
#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;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...