题目描述

难度分:$1500$

输入$T(\leq 10^4)$表示$T$组数据。所有数据的$n$之和$\leq 2 \times 10^5$。

每组数据输入$n(1 \leq n \leq 2\times 10^5)$和一个$1$~$n$的排列$p$。

每次操作，你可以从$p$中拿出两个数，把较小值放在$p$的开头（最左边），较大值放在$p$的末尾（最右边）。

要使$p$单调递增，至少要操作多少次？

输入样例

4
5
1 5 4 2 3
3
1 2 3
4
2 1 4 3
6
5 2 4 1 6 3

输出样例

2
0
1
3

算法

二分答案

比较容易发现以下的两个性质

1. 首先肯定是先操作排序后中间的两个数，然后不断往外扩展，直到最后一次操作最大值和最小值；
2. 其次这个问题是肯定有解的，大不了就操作$[\frac{n}{2}]$次（其中$[.]$表示对$.$向下取整）。

一开始一直在思考怎么低消耗模拟，后来发现存在单调性。操作$x$次能使排列$p$有序的话，那操作$x+1$次肯定更能使排列$p$有序（随便浪费一次操作即可）。

这样一来就好做了，如果操作了$x$次，那一定是$[1,x]$和$[n-x+1,n]$被分别排到了左右两侧，而$[x+1,n-x]$这些数仍然保持数组中的原有顺序放在中间。如果它们都已经有序了，那就说明操作$x$次就可以让排列$p$单调递增，这样就能够在$O(n)$的时间复杂度下检查操作$x$次能不能使得排列$p$变得有序。

复杂度分析

时间复杂度

二分的范围是$[0,[\frac{n}{2}]]$，时间复杂度为$O(log_2n)$，$check$的时间复杂度是$O(n)$，因此算法整体的时间复杂度为$O(nlog_2n)$。

空间复杂度

$check$的时候为了检查处于区间$[x+1,n-x]$的元素是否在原数组中保持有序，开辟了一个$seq$数组按照原数组$a$中的顺序来存储这些数，因此额外空间复杂度为$O(n)$。

C++ 代码

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>

using namespace std;
const int N = 200010;
int t, n, a[N];

bool check(int limit) {
    vector<int> seq;
    for(int i = 1; i <= n; i++) {
        if(limit < a[i] && a[i] <= n - limit) {
            seq.push_back(a[i]);
        }
    }
    return is_sorted(seq.begin(), seq.end());
}

int main() {
    scanf("%d", &t);
    while(t--) {
        scanf("%d", &n);
        for(int i = 1; i <= n; i++) {
            scanf("%d", &a[i]);
        }
        int l = 0, r = n>>1;
        while(l < r) {
            int mid = l + r >> 1;
            if(check(mid)) {
                r = mid;
            }else {
                l = mid + 1;
            }
        }
        printf("%d\n", r);
    }
    return 0;
}