题解：P17136 [KOI 2026 #1] 数列排序

qianyuzhe · 2026-07-25 16:07:51 · 题解

题意简述

给定序列 a，每次操作可选择 x，将 a 中 \le x 的元素按原顺序放到左侧，>x 的元素按原顺序放到右侧。求将 a 升序排序的最小操作次数。

题目分析

考虑排列怎么做。我们考虑 a 的逆排列 b，则一次操作可以理解为将 b 的一个前缀减少一个极大值，最后要使 b 不降。那么结论是显然的：最小操作次数即为 b 中相邻逆序对个数。

考虑不是排列怎么做。考虑对于 a 中相同的元素，再额外按照从左到右的顺序分配一个从小到大的标号。然后以其值为第一关键字、标号为第二关键字升序排序，并将其排序后的位置作为其新值，那么我们注意到这使 a 变为了排列且不改变答案。

实际实现时有更简单的写法。考虑上述做法的本质，我们记录每个值在 a 中最早出现的位置 l_i 和 r_i，然后对于某个值 i，设最大的比它小的值为 q，若 r_q>l_i 则令答案加一。

时空复杂度均为线性。

代码

#include<bits/stdc++.h>
using namespace std;
int n,a,q,c,i,l[300005],r[300005];
int main(){
    cin.tie(0)->sync_with_stdio(0);
    cin>>n;
    for(i=1;i<=n;i++){
        cin>>a;
        if(!l[a])l[a]=i;
        r[a]=i;
    }
    for(i=1;i<=n;i++){
        if(r[i]){
            c+=r[q]>l[i];
            q=i;
        }
    }
    cout<<c;
}