自动搬运

查看原文

来自洛谷，原作者为

	sccc_ scscscscscscscscscscscscscscscscscscscscscscscscscscscscscscscscscscscscscscscscscscscscscscscscscscscscscscsc

搬运于2025-08-24 22:57:02，当前版本为作者最后更新于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;
}