CF1372C. Omkar and Baseball（构造/数学）1500

题意

题目链接：Problem - 1372C - Codeforces

输入 t 表示 t 组数据，每组数据输入一个正整数 $n(1\leq n\leq 2e5)$ 和一个长为 n 的 1~n 的排列 a。
每次操作，你可以选择 a 的一个子数组，将其错排（错排前后，子数组同一位置上的元素不能相同）。
输出将 a 变为升序，至少需要几次操作。

例如如果一个连续序列是2 3 4，如果想要变成4 3 2，因为3的位置没有变，所以3 4 2和4 2 3都是可以的。

思路

大胆猜测！最多只需要两次即可，那么什么时候零次什么时候一次。

零次的时候当然就是一直是a[i]==i，1的时候就是需要去判断最大的需要错排的区间里面判断是否有a[i]==i的。

何为最大的需要错排的区间，例如:1,2,3,[7,6,5,4],8,9，这里面的3,7,6,5,4就需要错排，所以就需要去看这里面是否有“不动”的，如果有则还需要一次

代码

inline void Case_Test()
{
    cin>>n;
    bool ok = true;
    for (int i=1;i<=n;i++)
    {
        cin>>a[i];
        if (a[i]!=i) ok = false;
    }
    if (ok) {cout<<0<<endl;return;}
    int l = 1, r = n;
    while (l<=n&&a[l]==l) l++;
    while (r>=1&&a[r]==r) r--;
    ok = false;
    for (int i=l;i<=r;i++)
        if (a[i]==i) ok = true;
    if (ok) cout<<2<<endl;
    else cout<<1<<endl;
}

灵神方法：

package main

import (
    "bufio"
    . "fmt"
    "os"
)

// github.com/EndlessCheng/codeforces-go
func main() {
    in := bufio.NewReader(os.Stdin)
    var T, n, v int
    for Fscan(in, &T); T > 0; T-- {
        Fscan(in, &n)
        c := 0
        for i, pre := 1, true; i <= n; i++ {
            Fscan(in, &v)
            if v == i != pre {
                c++
                pre = !pre
            }
        }
        if c == 2 {
            c = 1
        } else if c > 2 {
            c = 2
        }
        Println(c)
    }
}