[IAMOI R4] 木桶效应 题解

· · 题解

思路

观察答案为“最小值最大”，发现答案单调，考虑二分答案 ans，将问题转换成：能否通过一种铺木板的方式，使得所有木板的长度都不小于 ans。

考虑贪心。

将问题转化为，有若干个长度为 ans-a_i 的缝隙，问能否用 m 个长度为 1 和 k 个长度为 h 的木板填充所有的缝隙。

假设对于某个缝隙，我们用总长度为 l 的木板填充了这个缝隙，我们称这个缝隙被填满，当且仅当 l \ge ans-a_i。我们定义一个填满的缝隙的剩余长度为 l-(ans-a_i)。显然，我们希望多余长度之和尽可能小（因为这样子“浪费”就少）。

发现长度为 1 的木板比长度为 h 的更好用，可以对缝隙进行细微的调整，因此我们考虑先用 h 填充，再用 1 填充。

首先按任意顺序，对于每个缝隙，用长度为 h 的木板进行填充，直到它与 ans 的高度差小于 h，也就是说不会填充使得木板长度超出 ans。发现这样操作一定不劣。

接着，如果还有多余的长度为 h 的木板，则按照与 ans 的高度差（可以证明这个高度差一定是 (ans-a_i)\bmod h）从大到小填充。这样子可以做到多余长度之和最小，也可以保证剩余的未填充的缝隙长度之和最小。

最后再用长度为 1 的木板填充剩余空隙即可。如果填充时遇到某个缝隙没有足够的长度为 1 的木板去填充，由于我们已经保证剩余的未填充的缝隙长度之和最小，因此就说明无法填充所有缝隙。

如果在 check 的时候直接排序，复杂度为 O(n\log n\log V)。

发现可以在二分前按照 a_i\bmod h 从小到大排序，二分时处理一下便可以使得处理多余的长度为 h 的木板时是按照与 ans 的高度差从大到小填充的，复杂度便降为 O(n\log V)。

但是没有卡双 \log。

code

双 \log 懒人实现。

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+5;
int n,m,k,h,c,p,lm,lk,l,r=1e18,mid,a[N],b[N];
bool check(int x){
    c=0;
    for(int i=1;i<=n;i++) if(a[i]<x) b[++c]=x-a[i];
    if(!c) return true;
    lm=m;
    lk=k;
    for(int i=1;i<=c;i++){
        p=min(b[i]/h,lk);
        b[i]-=p*h;
        lk-=p;
    }
    sort(b+1,b+c+1,greater<int>());
    for(int i=1;i<=c;i++){
        if(lk&&b[i]>0){
            b[i]-=h;
            lk--;
        }
    }
    for(int i=1;i<=c;i++){
        if(lm-max(b[i],0ll)<0) return false;
        lm-=max(b[i],0ll);
    }
    return true;
}
signed main(){
    scanf("%lld%lld%lld%lld",&n,&m,&k,&h);
    for(int i=1;i<=n;i++) scanf("%lld",&a[i]);
    while(l<=r){
        mid=l+r>>1;
        if(check(mid)) l=mid+1;
        else r=mid-1;
    }
    printf("%lld",r);
    return 0;
}