题解：P12000 扶苏出勤日记

Motonic_queues · 2025-03-30 17:06:20 · 题解

awmc

题目大意

每天赚 b_i 块钱，1 块钱可以换 a_i 个币去打乌蒙，求每天打乌蒙的最多次数。

题意分析

显然的二分，那么难点在于考虑 check。

check 能想到采用模拟思路，把 n 天遍历一边，先赚钱，然后换币。如果中途币不够了就 return 0，能过完这 n 天就 return 1。

考虑如何换币：假设 a_i<a_j (i<j)，而且第 i 天的币足以用到第 j 天，那么显然在第 j 天换币比在第 i 天换币更优。
更特别的，如果 j 离 i 最近，那么它们中间的日子换币一定比这两天换币更劣，考虑到这点，使用单调栈维护。

分类讨论，假设每天要打 x 把，现在是第 i 天，有 B 个币， M 块钱，更优的下一天是 nxt_i。

如果当前这一天是之后最优的一天，也就是说 nxt_i 不存在，那么把钱全部花光就好了，反正最优。

那一天存在的话，有 3 种情况：
第一：当前的币已经足够支撑到那一天，即

那么一块钱都不用花。

第二：花一部分钱可以使上面的式子成立，也就是说

那么花最少的钱，因为剩下的要留给第 nxt_i 天。

第三：钱花完了也不能使上面的式子成立。
只能在这里把钱全部花完，因为留不到那一天，如果留给中间的日子反而劣，所以最好的是自己用完。

总的就上面几种情况，依次判断即可。

代码&细节

二分上界是 10^{12}。

#include<bits/stdc++.h>
#define int long long
using namespace std;

const int N=1e6+5;
int T,n;
int a[N],b[N],nxt[N];
int kkk;//第4种情况下花的钱

bool chk(int x){
    int now=0,B=0;
    for(int i=1;i<=n;i++){
        now+=b[i];
        int days=nxt[i]-i;
        if(nxt[i]==-1){ //当前最优
            B+=now*a[i];
            now=0;
        }else{
            if(now*a[i]>=x*days-B){ //钱够
                kkk=ceil(1.0*max(x*days-B,0ll)/a[i]); //计算最少需要花的钱
                B+=kkk*a[i];
                now-=kkk;
            }else{ //钱不够
                B+=now*a[i];
                now=0;
            }
        }
        if(B>=x)B-=x;
        else return 0;
    }
    return 1;
}

stack<int> s;
signed main(){
    ios::sync_with_stdio(0);cin.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];
        for(int i=1;i<=n;i++){ //维护单调栈
            while(!s.empty()&&a[s.top()]<=a[i]){nxt[s.top()]=i;s.pop();}
            s.push(i);
        }
        while(!s.empty())nxt[s.top()]=-1,s.pop();
        int l=0,r=1e12,mid;
        while(l<r){
            mid=(l+r+1>>1);
            if(chk(mid))l=mid;
            else r=mid-1;
        }
        cout<<l<<'\n';
    }
    return 0;
}

呜呜呜别卡我常