P10334 题解

· · 题解

upd：20250119 在代码被 hack 了之后改成了正确时间复杂度的。

一道有意思的单调栈题。

首先，先来分析题意，每个时间可以生产一杯果汁，固定的时间会有人拿走当前最大的一杯果汁，且要求比他期望的大。求榨果汁最少的体积。

可以发现，每杯果汁都要尽量靠后做。

如果有一个人 a ，他将在第 i (i<a) 个时间时来取，那么一定无法满足，因为果汁机一次只能做一杯果汁，输出 -1 即可。

那么当每个人来取果汁的时间均不同时，就可以做好就取。 否则，如果有 k (k\ge2) 个人在同一时间来取果汁，就要提前 k 个时间做好这 k 杯果汁。但是如果再提前做果汁的这 k 个时间内，有其他人会来取果汁呢？

这并不是将剩余 k 未做好的果汁向前移就行了。因为取果汁的人会取走当前最大的一杯果汁，所以像样例 2 中的这种情况，如果要提前制作一杯果汁，且这杯果汁要在一些人取走果汁后才会被取走，那么中途的这些人的果汁就得做得比提前制做的那杯果汁大。这样就完美解决了这个问题。

接下来就分析一下代码，可以从后往前看（毕竟需要提前做的果汁一定是从后往前排的）由于 t_n\le 10^9,所以可以从第 t_n 个时间枚举到 1 比较每个时间与顾客到来的时间即可。

但是后来这种做法被 Hack 了，所以我加了个二分查找，每次找下一个人的时间，预留一些时间给排在队列中的果汁。减少了一些不必要的循环。

Tips：如果您 WA on #18 那么请开 long long

#include <bits/stdc++.h>
using namespace std;
stack <int> st;
int t[350000],m[350000];
long long ans;
int main(){
    int n;
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>t[i];
        if(t[i]<i){
            cout<<-1;
            return 0;
        }
    }
    for(int i=1;i<=n;i++){
        cin>>m[i];
    }
    int dw=n;
    for(int i=t[n];i>=1;i--){
        i=min(i,int(st.size()+t[upper_bound(t+1,t+n+1,i)-t-1]));
        //查找下一个人，预留st.size()个空位给将要来的人。 
        if(t[dw]<i){
        //当下一个人还没来取果汁时，就可以先制作后面的
            if(st.size()){
                ans+=st.top();
                st.pop();
            }
        }else if(t[dw]==i){
        //当下一个人已经来取果汁时，就立刻制作他的
            if(st.size()) st.push(max(st.top(),m[dw]));
            else st.push(m[dw]);
            dw--,i++;
        }else if(t[dw]>i) dw--,i++;
      //当下一个人和上一个人同时取果汁时就要存到栈里提前制作。
    }
    while(st.size()){
        ans+=st.top();
        st.pop();
    }
    cout<<ans;
    return 0;
}

这是蒟蒻的第二篇题解，支持一下孩子吧！