P76036 给水箱加水 — 题解

专题： 二分答案
适用题目： 新生 OJ 本地题包中的 P76036，不要直接用于外站同名题。

解题思路

检查目标水位 h 是否可行：对所有低于 h 的柱子求需要补充的水，若不超过预算则可行；对 h 二分。

复杂度

每组 $O(n\log (\max a_i+x+1))$。

易错点

累计用水可能很大，必须用 64 位整数；超过预算可以提前停止。

C11 参考程序

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
#include <limits.h>

int feasible(const long long *a,int n,long long water,long long h){
    long long cost=0;
    for(int i=0;i<n;i++)if(a[i]<h){
        cost+=h-a[i];if(cost>water)return 0;
    }
    return 1;
}
int main(void) {
    int t;scanf("%d",&t);
    while(t--){int n;long long x;scanf("%d%lld",&n,&x);
        long long *a=malloc(n*sizeof(long long)),mx=0;
        for(int i=0;i<n;i++){scanf("%lld",&a[i]);if(a[i]>mx)mx=a[i];}
        long long l=0,r=mx+x+1;
        while(l+1<r){long long mid=l+(r-l)/2;
            if(feasible(a,n,x,mid))l=mid;else r=mid;
        }
        printf("%lld\n",l);free(a);
    }
    return 0;
}

C++17 参考程序

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define nl '\n'

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t;
    cin>>t;
    while(t--){
        int n;
        ll x;
        cin>>n>>x;
        vector<ll>a(n);
        for(auto &v:a)cin>>v;
        ll l=0,r=*max_element(a.begin(),a.end())+x+1;
        while(l+1<r){
            ll mid=l+(r-l)/2;
            ll need=0;
            for(auto v:a)if(v<mid)need+=mid-v;
            if(need<=x)l=mid;
            else r=mid;
        }
        cout<<l<<nl;
    }
    return 0;
}

题解建议设置为训练结束后开放。普通判题无法验证是否实际使用指定函数或 STL。