自动搬运

查看原文

来自洛谷，原作者为

	Loser_Syx 不可逆の方が美しいから

搬运于2025-08-24 22:52:03，当前版本为作者最后更新于2024-01-25 09:48:49，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

有一个贪心策略：对于 $1 \sim g_i$ 的登机口，一定是选最靠近 $g_i$ 的那个没被使用的登机口。

具体来看看为什么，记刚刚那个数字为 $k$，对于 $g_j < k$ 的 $j$，$j$ 一定去不到那个登机口，对这个无影响，对于 $g_j > k$ 的 $j$，$j$ 的选择一定是比现在的 $i$ 要多的，而因为我们需要停的最多，所以要给 $i$ 留一个位置。

并查集维护最近的 $k$ 即可。

const int N=1e5+19;
struct DSU {
	int f[N];
	void init(int n) {
		for (int i=1;i<=n;++i) f[i]=i;
	}
	int find(int x) {
		if (f[x]==x) return x;
		return f[x]=find(f[x]);
	}
	void merge(int x) {
		f[x]=find(x-1);
	}
} dsu;
signed main(){
	int n, m;
	read(n, m);
	dsu.init(n);
	for (int i=1;i<=m;++i) {
		int x=read();
		if (dsu.find(x)==0) return write(i-1,'\n'),0;
		dsu.merge(dsu.f[x]);
	}
	write(m,'\n');
	return 0;
}