ARC181总结

zzy-hhh / 2024-08-07 / 原文

ARC181总结

ARC还是太难了

A

标签: 有脑子🧠都会

题意

问题陈述

给出 $(1,2,\dots,N)$ 的排列 $P=(P_1, P_2,\dots,P_N)$ 。

您希望通过执行以下操作零次或多次来满足所有 $i=1,2,\dots,N$ 的 $P_i = i$ ：

-选择整数 $k$ ，如T

帽子 $1 \leq k \leq N$ 。如果 $k \geq 2$ ，则按升序对 $P$ 的第 $1$ 至第 $(k-1)$ 项进行排序。然后，如果 $k \leq N-1$ ，则按升序对 $P$ 的第 $(k+1)$ 到第 $N$ 项进行排序。可以证明在该问题的约束条件下，

对于所有 $i=1,2,\dots,N$ ，可以满足 $P_i=i$ ，而对于任何 $P$ ，可以进行有限次数的运算。查找所需的最小操作数。

code:

#include <bits/stdc++.h>

using namespace std;

#define endl '\n'

#define TRACE 1
#define tcout TRACE && cout

#define fst ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);

#define int long long

const int P = 998244353; 
const int Base = 3221225477;
const int INF = 0x3f3f3f3f3f3f3f3f; 

const int N = 1e6 + 10, M = 2e6 + 10; 

int n;
int a[N];

void solve()
{
    cin >> n;
    bool flag = true;
    for(int i=1; i<=n; i++)
    {
        cin >> a[i];
        if(a[i] != i)
        {
            flag = false;
        }
    }
    if(flag == true)
    {
        cout << 0 << endl;
        return;
    }
    int maxn = 0;
    for(int i=1; i<=n; i++)
    {
        if(a[i] == i && maxn < a[i])
        {
            cout << 1 << endl;
            return;
        }
        maxn = max(a[i], maxn);
    }
    if(a[1] == n && a[n] == 1)
    {
        cout << 3 << endl;
        return;
    }
    cout << 2 << endl;
}

signed main()
{
	int t;
	cin >> t;
	while(t--)
	{
	    solve();
	}
	return 0;
}