题解：P12000 扶苏出勤日记

又有题可以发题解啦。

题目大意

第 $i$ 天可以收入 $b_i$，1块可以换 $a_i$ 个游戏币，每个游戏币能去玩无梦，问每天最多玩多少。

思路

显然，这道题具有单调性，所以可以用二分。

那 check 该如何考虑？

1. 单调栈，记录一个 $p_i$，为第 $i$ 天的下一个更优的 $a_i$（即 $a_{p_i} > a_i$）。
2. 贪心，尽量在 $a_i$ 大的天购买更多的游戏币。
3. 验证，如果今天的钱都不够满足今天的需求（也就是玩 $mid$ 次），就直接返回 false。

代码实现

#include<bits/stdc++.h>
using namespace std;
#define int long long//不开long long见祖宗
int n, a[1000010], b[1000010], p[1000010];
bool check(int x)
{
    int now = 0, sum = 0;//now为当天可以玩的次数，sum为当前有的钱
    for(int i = 1; i <= n; i++)
    {
        sum += b[i];//增加钱
        if(p[i])//如果后面有比今天a[i]更优的
        {
            //我的a_i是在i~p[i]中最优的
            int need = (p[i] - i) * x;
            if(now < need)//如果当前不够
            {
                int t = need - now;
                int buy = min((t + a[i] - 1) / a[i], sum);
                now += buy * a[i];
                sum -= buy;
            }
        }
        else
            now += sum * a[i], sum = 0;//当前最优，全部兑换完
        now -= x;
        if(now < 0) return false;
    }
    return true;
}
int binary()
{
    int l = 0, r = 1e12, mid, ans = -1;
    while(l <= r)
    {
        mid = (l + r) / 2;
        if(check(mid)) l = mid + 1, ans = mid;
        else r = mid - 1;
    }
    return ans;
}
signed main()
{
    int T;
    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];
        /*预处理p*/
        stack<int> s;
        for(int i = n; i >= 1; i--)
        {
            while(!s.empty() && a[s.top()] <= a[i]) s.pop();
            if(s.empty()) p[i] = 0;
            else p[i] = s.top();
            s.push(i);
        }
        /*******/
        int ans = binary();
        cout << ans << endl;
    }
    return 0;
}