题解：P10334 [UESTCPC 2024] 饮料

chrisgr · 2024-11-28 10:59:21 · 题解

无解

容易发现前 t 分钟最多做 t 瓶饮料，所以当 第 i 个人需要在小于 i 的时间取走饮料时，无解。
即存在 t_i<i 时无解，其余情况均有解。

求解

注意到第 i 个人会取走当前最大的饮料，所以我们可以反向枚举 i 进行求解，先分配大于 t_i 的时间里制作的饮料大小，并将当前的饮料与栈顶饮料的最大值入栈作为当前会拿走的饮料大小。

正确性显然，时间复杂度 \mathcal{O}(n) 轻松切过本题。

CODE

#include<bits/stdc++.h>
using namespace std;
const int N = 2e5 + 5;
int n, t[N], a[N], stk[N], tp;
long long ans;
int main() {
    scanf("%d", &n);
    bool as = 0;
    for(int i = 1; i <= n; ++i) {
        scanf("%d", t + i);
        if(t[i] < i) as = 1;
    }
    for(int i = 1; i <= n; ++i) scanf("%d", a + i);
    if(as) puts("-1");
    else {
        int now = t[n];
        for(int i = n; i; --i) {
            while(tp && now > t[i]) --now, ans += stk[tp--];
            stk[tp] = max(stk[tp++], a[i]);
            now = t[i];
        }
        while(tp) ans += stk[tp--];
        printf("%lld", ans);
    }
    return 0;
}