题解：P12000 扶苏出勤日记

· · 题解

题外话

不知道为什么，赛时第一感觉就是 ST 表，全然忘了单调队列。但理论上 ST 表也是 O(n\log n)，和单调队列没区别。但可能是被卡常了吧就是没过去（80 分），本文最后有我没过的 ST 表代码，请大佬们看看出了什么问题。

思路

首先观察到答案有单调性，可以二分答案。分别枚举每一天的花钱情况。假设我们有第 i 天的收入 x 元，在第 j 天我们可以最多得到 x\times \max^{j}_{k=i} a_k。所以我们可以以此贪心。而 \max^{j}_{k=i} a_k 这个东西，我的第一反应是 ST 表，但却不知为何超时。再次转变思路，发现我们发现最大值是单调递增的，所以一定是第 i 天的钱花完后我们再去花第 i+1 天的钱，所以 i 的变化是每次加一。而 j 是我们枚举的，也是每天加一。这个不就是滑动窗口（单调队列模板）吗？所以最终复杂度 O(n\log n)，瓶颈在二分。

代码

正解代码：

#include<bits/stdc++.h>
#define int long long
using namespace std;
int t,n,a[1000005],b[1000005],c[1000005],q[1000005];
bool check(int x){
    for(int i=1;i<=n;i++)c[i]=b[i];
    int jl=1,ys=0,h=0,r=-1;
    for(int i=1;i<=n;i++){
        while(h<=r&&a[q[r]]<=a[i])r--;
        q[++r]=i;
        int y=x;
        if(y<=ys)ys-=y,y=0;
        else y-=ys,ys=0;
        while(jl<=i&&y>0){
            int tmp=min((int)ceil(1.0*y/a[q[h]]),c[jl]);
            y-=tmp*a[q[h]];
            c[jl]-=tmp;
            if(c[jl]==0){
                if(q[h]==jl)h++;
                jl++;
            }
        }
        if(y>0)return 0;
        ys+=-y;
    }
    return 1;
}
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    cin>>t;
    while(t--){
        cin>>n;
        for(int i=1;i<=n;i++)cin>>a[i];
        for(int i=1;i<=n;i++)cin>>b[i];
        int l=0,r=1e12,mid,ans=0;
        while(l<=r){
            mid=(l+r)/2;
            if(check(mid))ans=mid,l=mid+1;
            else r=mid-1;
        }
        cout<<ans<<"\n";
    }
    return 0;
}

ST 表 80 分代码：

#include<bits/stdc++.h>
#define int long long
using namespace std;
typedef int type;
inline int read(){
    int x=0,f=1;
    char ch=getchar_unlocked();
    while(!isdigit(ch)){
        if(ch=='-')f=-1;
        ch=getchar_unlocked();
    }
    while(isdigit(ch)){
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar_unlocked();
    }
    return x*f;
}
inline void write(long long x){
    if(x<0)putchar_unlocked('-'),x=-x;
    if(x>9)write(x / 10);
    putchar_unlocked(x%10+'0');
}
int t,n,a[1000005],b[1000005],c[1000005],LOG[1000005],ST[1000005][25];
void build_log(){
    LOG[0]=-1;
    for(int i=1;i<=1000000;i++)LOG[i]=LOG[i/2]+1;
}
void build_st(){
    for(int i=1;i<=n;i++){
        ST[i][0]=a[i];
    }
    for(int j=1;j<=20;j++){
        for(int i=1;i+(1<<j)-1<=n;i++){
            ST[i][j]=max(ST[i][j-1],ST[i+(1<<j-1)][j-1]);
        }
    }
}
int find(int l,int r){
    int w=LOG[r-l+1];
    return max(ST[l][w],ST[r-(1<<w)+1][w]);
}
bool check(int x){
    for(int i=1;i<=n;i++)c[i]=b[i];
    int jl=1,ys=0;
    for(int i=1;i<=n;i++){
        int y=x;
        if(y<=ys)ys-=y,y=0;
        else y-=ys,ys=0;
        while(jl<=i&&y>0){
            int tmp=min((int)ceil(1.0*y/find(jl,i)),c[jl]);
            y-=tmp*find(jl,i);
            c[jl]-=tmp;
            if(c[jl]==0)jl++;
        }
        if(y>0)return 0;
        ys+=-y;
    }
    return 1;
}
signed main() {
    build_log();
    t=read();
    while(t--){
        n=read();
        for(int i=1;i<=n;i++)a[i]=read();
        for(int i=1;i<=n;i++)b[i]=read();
        build_st();
        int l=0,r=1e12,mid,ans=0;
        while(l<=r){
            mid=(l+r)/2;
            if(check(mid))ans=mid,l=mid+1;
            else r=mid-1;
        }
        write(ans),putchar('\n');
    }
    return 0;
}