[CF1372C] Omkar and Baseball

[CF1372C] Omkar and Baseball - 构造

Description

给你一个 (1) 到 (n) 的排列。选择一段区间 ([l,r])，使得此段区间上的数交换后都不在原来的位置。问最少多少次可以将此排列变成升序的。

Solution

如果一个位置 i 满足 ai=i，那么我们说，这个位置是好的

显然答案不会超过 2，第一步全部打乱，第二步全部归位

如果所有位置都是好的，那么显然不需要进行任何操作

如果存在一个区间没有位置是好的，其它位置都是好的，那么显然可以通过一次交换结束

#include <bits/stdc++.h>
using namespace std;

#define int long long

signed main()
{
    ios::sync_with_stdio(false);

    int t;
    cin >> t;

    while (t--)
    {
        int n;
        cin >> n;

        vector<int> a(n + 2);
        for (int i = 1; i <= n; i++)
            cin >> a[i];

        int flag = 0;
        for (int i = 1; i <= n; i++)
        {
            if (flag == 0 && a[i] != i)
                flag = 1;
            if (flag == 1 && a[i] == i)
                flag = 2;
            if (flag == 2 && a[i] != i)
                flag = 3;
        }

        if (flag == 3)
            cout << 2 << endl;
        else if (flag == 0)
            cout << 0 << endl;
        else
            cout << 1 << endl;
    }
}