自动搬运

查看原文

来自洛谷，原作者为

	佬头 {暴力出奇迹，骗分过样例，暴搜挂着机，打表出省一}ด้้้้้็้้้็็็็็้้้้้็็็็็้้้้้้็็็็็้้้้้็็็็็้้้้้้็็็็็้้้้้็็็็็้้้้้้็็็็็้้้้้็็็็็้้้้(已退役)

搬运于2025-08-24 22:50:39，当前版本为作者最后更新于2023-09-30 10:45:08，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

Description

给定一个 $n$ 的排列 $A$。请你利用 $m$ 个栈（初始都为空）对 $A$ 排序：按照 $a_1,a_2,\dots,a_n$ 的顺序，将每个数压入其中一个栈的栈顶。所有数入栈后，每次选定一个栈并将其所有元素弹出，使得最后弹出栈的数依次为 $1,2,…,n$。求最小的 $m$。

Solution

显然栈中的元素一定满足 $b_{i+1}=b_i-1$（若存在）。因此对于一个 $a_i$，我们在已有栈中寻找是否有一个栈的栈顶元素满足 $b_{top}=a_i+1$。若存在，压入这个栈中；否则，新开一个栈，并压入其中。最终栈的个数就是答案。

考虑开一个 bool 数组维护此时的某个元素是否可以压入某个栈中。（总不能真的去维护 $m$ 个栈然后暴力搜索栈顶吧？）

时间复杂度 $\mathcal{O}(Tn)$。

Code

#include <iostream>
using namespace std;
int n, ans;
bool vis[500005]; //vis[i]:此时第i位可以并入之前的栈
int read(){
	int x = 0;
	char a = getchar();
	while(a < '0' || a > '9') a = getchar();
	while('0' <= a && a <= '9') x = (x << 1) + (x << 3) + (a ^ 48), a = getchar();
	return x;
}
void write(int x){
	if(x > 9) write(x / 10);
	putchar(x % 10 | 48);
}
int main(){
	for(int _ = read(); _ >= 1; _ --){
		n = read(), ans = 0;
		for(int i = 1; i <= n; ++ i) vis[i] = 0;
		for(int i = 1; i <= n; ++ i){
			int a = read();
			if(!vis[a]) ++ ans;
			vis[a - 1] = 1;
		}
		write(ans), puts("");
	}
	return 0;
}