题解：P10334 [UESTCPC 2024] 饮料

Tsuki091117 · 2024-07-12 09:07:59 · 题解

题目大意

给定 n 个人取饮料的时间及希望得到饮料的体积。

每个人拿饮料时都会拿走当前所剩饮料中体积最大的那一个。

求是否有解使得每个人拿到的饮料体积大于等于期望得到的饮料体积，无解输出 -1，有解输出最小体积和。

题目分析

无解情况

由于机器每分钟都可以制作任意体积的饮料，那么只要我取饮料的时间大于等于我排队的编号就一定有解，故当取饮料的时间小于排队的编号就一定无解，此时输出 -1 即可。

有解情况

因为有些人会同时取饮料，如果正着走有些麻烦，那么我们就反着走（正难则反）。

情况如下

1.当 t_{now}=i 时，说明当前时间有人来取饮料，那么我们先给他制作，但当前所制作饮料不能小于后面提前制作的饮料（因为要保证提前制作的饮料不会被抢走）。

2.当 t_{now} <i 时，说明这个人在此之前取饮料，所以不用管它，当前时间就可以用来做后面需要提前制作的饮料。

3.当 t_{now}>i 时，说明这个人取饮料的时间在此之后，也就是说他需要提前制作饮料。

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e5+10;
int n,ans;
stack<int> stk;//存储未制作的饮料（需提前制作的饮料） 
struct node{
    int a,t,k;
}p[N];//a:期望得到的体积  t:取饮料时间 k:出现编号，便于下面的排序 
bool cmp(node a,node b){
    return a.t<b.t||(a.t==b.t&&a.k<b.k);//排序（如果同时取饮料，根据出现时间排序） 
}
signed main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>p[i].t;
        p[i].k=i;//记录出现的编号 
    }
    for(int i=1;i<=n;i++){
        cin>>p[i].a;
    }
    sort(p+1,p+n+1,cmp);
    for(int i=1;i<=n;i++){
        if(p[i].t<p[i].k){
            cout<<"-1";
            return 0;
        }//如果取饮料的时间小于编号，机器无法制作，无解 
    }
    int now=n;//逆向 
    for(int i=p[n].t;i>=1;i--){
        if(p[now].t==i){
            if(stk.size()) stk.push(max(p[now].a,stk.top()));
            else stk.push(p[now].a);
            now--;
            i++;
        }//如果当前时间有人来取饮料，先给他制作 
        else if(p[now].t<i){
            if(stk.size()){
                ans+=stk.top();
                stk.pop();
            }
        }//如果这个人不着急，先制作需提前制作的 
        else{
            now--;
            i++;
        }//这个人需提前制作 
    }
    while(stk.size()){
        ans+=stk.top();
        stk.pop();
    }//加上stk中剩余的 
    cout<<ans;//输出答案 
    return 0;
}