[ICPC2022 Jinan R] Stack Sort

佬头 · 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;
}