基于二分查找与插入的快速排序题解

良心WA题人 · 2024-01-13 20:25:03 · 题解

首先，a_n\not=n 无解。

对于操作过程，考虑一种方案：

从大到小枚举 i

• 若 p_i\not=i 则操作使得 p_j=i 的 j。

尝试证明上述算法的正确性。显然经过上述操作后可以完成排序。而每次操作将会把序列变为：

若之前操作 1 到 j-1 中的数，则必然不会跨过 j，则在 j 操作后必然还需要再进行操作。

若之前操作了 j+1 到 i-1 中的数，则先操作 j 再操作这中间的数对答案没有影响。

上述操作按理来讲可以通过一些数据结构直接维护。但是这显然太麻烦了。考虑去观察哪些情况下 i 不会被操作，可以发现 i 不被操作当且仅当 p_i 为 i 开始的后缀的最小值。

证明比较简单，首先若中间存在小于 p_i 的数则 i 必然比这个数先操作，那么相对位置不会变化，则 i 后面不可能为 i+1 到 n 这些全都比它大的数。

而若不存在，则任何比 p_i 小的数无法到 p_i 后方，所以当 p_i 操作时右侧均比 p_i 大，显然满足要求。故得证。

#include<bits/stdc++.h>
using namespace std;
const int NN=2e6+4;
int a[NN];
int main()
{
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);
    if(a[n]!=n)
    {
        printf("-1");
        return 0;
    }
    int minn=1e9,ans=0;
    for(int i=n;i>=1;i--)
    {
        if(a[i]<minn)
            minn=a[i];
        else
            ans++;
    }
    printf("%d",ans);
    return 0;
}