题解：P10334 [UESTCPC 2024] 饮料

无解

容易发现前

t

分钟最多做

t

瓶饮料，所以当第

i

个人需要在小于

i

的时间取走饮料时，无解。
即存在

t_i<i

时无解，其余情况均有解。

求解

注意到第

i

个人会取走当前最大的饮料，所以我们可以反向枚举

i

进行求解，先分配大于

t_i

的时间里制作的饮料大小，并将当前的饮料与栈顶饮料的最大值入栈作为当前会拿走的饮料大小。

正确性显然，时间复杂度

\mathcal{O}(n)

轻松切过本题。

CODE

CPP

#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;
}

题解：P10334 [UESTCPC 2024] 饮料

文章操作

无解

求解

CODE

相关推荐

评论

题解：P10334 [UESTCPC 2024] 饮料