翻译及题解

翻译：

题目背景

Bessie 和 Elsie 正在帮助 Farmer John 洗碗，这是一个比人们想象的更复杂的过程。

题目描述

两头奶牛决定 Bessie 负责涂肥皂，Elsie 负责冲洗。

刚开始的时候，$N$ 个脏盘子（保证是从 $1$ 到 $N$ 的一个排列）堆在 Bessie 那里，而 Elsie 这边的堆是空的。而在她们俩之间，则有一张专门放涂过肥皂的盘子的桌子。

每个冲洗步骤需要执行以下两个操作之一：

• Bessie 从脏盘子堆顶取出一个盘子，涂上肥皂，然后放在桌子上。将这个盘子放在桌子上时，Bessie 只能放在现有的非空盘堆的顶端，或是在最右边新增一个盘堆。
• Elsie 从桌子最左边的盘堆的顶端拿起盘子，将它冲洗后放在干净的盘堆顶端。

她们希望干净的盘堆能按编号排序，编号最小的在底端，编号最大的在顶端。然而她们发现有的时候这并不可能做到。现在给定脏盘子的堆叠顺序，请你求出一个最大前缀，使得该前缀的所有盘子洗干净后，能按上面的要求堆叠。

输入格式

第一行一个整数 $N$（$1 \leq N \leq 10^5$）。

接下来 $N$ 行，每行一个整数，代表 Bessie 的脏盘子堆的堆叠顺序。输入的第一个盘子在堆的顶部。

输出格式

输出该序列的最大前缀长度，使得该前缀的所有盘子洗干净后，能按小号在下，大号在上的规则堆叠。

样例 #1

样例输入 #1

5
4
5
2
3
1

样例输出 #1

4

题解：

#include<bits/stdc++.h>
using namespace std;
int n,placed,base[100010];
vector<int> item[100010];
int main()
{
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		int x;
		cin>>x;
		if(x<placed)
		{
			cout<<i-1;
			return 0;
		}
		for(int j=x;j>0&&!base[j];j--)
			base[j]=x;
		while(!item[base[x]].empty()&&item[base[x]].back()<x)
		{
			placed=item[base[x]].back();
			item[base[x]].pop_back();
		}
		item[base[x]].push_back(x);
	}
	cout<<n;
	return 0;
}