自动搬运

查看原文

来自洛谷，原作者为

	45dino 不要停下来啊>_<

搬运于2025-08-24 22:17:24，当前版本为作者最后更新于2020-03-17 18:43:47，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

这道题还是挺考验思维的，我思考了一下午才AC。

我才不会告诉你我是边水犇犇边玩candybox边玩巴克球边写英语作业边做题的，其实真正代码只写了5min。

把问题转换成人话，就是要求前ans个脏盘子必须按顺序排列,输出ans（注意是输入的前ans个而不是编号的前ans个）。

还是看不懂？手玩一下样例：

看完这排版极为凌乱的图后，有没有一种一脸懵逼茅塞顿开的感觉呢，如果有，就试着写一写吧。

附上喜闻乐见的代码：

#include<bits/stdc++.h>
using namespace std;
int n,placed,base[100001];
vector<int> item[100001];
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;
}