P9812

Loser_Syx · 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;
}