题解：P10334 [UESTCPC 2024] 饮料

sccc_ · 2025-01-06 21:41:56 · 题解

Solution

一道单调栈题。

贪心原则：

饮品能当时做就当时做，不能就提前做。

无解情况：

当任意时间 i 我们需要做 \geq i 数量的饮品，那就不成立。

如果有多个重复的时间，我们分类。

• 如果单调栈顶元素 \geq 当前元素，我们当然要加上栈顶元素，否则顾客就会选择栈里的元素，条件不成立。

• 否则，我们不能加上栈里元素，需要加上当前元素，否则顾客就不满意了。

否则，我们就去制作在栈里的元素，再判断刚刚需要判断的操作。

注意开 long long。

Code

#include <bits/stdc++.h> 
using namespace std;

#define int long long
const int N = 200005;
int n;
int t[N];
int a[N];
int s[N];
int top;

signed main()
{
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        cin >> t[i];
        if (i > t[i])
            return cout << -1, 0;
    }
    for (int i = 1; i <= n; i ++)
        cin >> a[i];
    s[++ top] = a[n];
    int sum = a[n];
    for (int i = n - 1; i >= 1; i --)
    {
        if (t[i] == t[i + 1])
        {
            if (s[top] >= a[i])
            {
                int x = s[top];
                sum += x;
                s[++ top] = x;
            }
            else
            {
                sum += a[i];
                s[++ top] = a[i];
            }
        }
        else
        {
            for (int j = 1; j <= t[i + 1] - t[i]; j ++)
            {
                if (top != 0)
                    top --;
                else
                    break;
            }
            if (s[top] >= a[i])
            {
                int x = s[top];
                s[++ top] = x;
                sum += x;
            }
            else
            {
                s[++ top] = a[i];
                sum += a[i];
            }
        }
    }
    cout << sum;
    return 0;
}