CodeForce 1372 C-Omkar and Baseball(思考)

C. Omkar and Baseball
time limit per test 2 seconds memory limit per test 256 megabytes input standard input output standard output Patrick likes to play baseball, but sometimes he will spend so many hours hitting home runs that his mind starts to get foggy! Patrick is sure that his scores across n sessions follow the identity permutation (ie. in the first game he scores 1 point, in the second game he scores 2 points and so on). However, when he checks back to his record, he sees that all the numbers are mixed up!
Define a special exchange as the following: choose any subarray of the scores and permute elements such that no element of subarray gets to the same position as it was before the exchange. For example, performing a special exchange on [1,2,3] can yield [3,1,2] but it cannot yield [3,2,1] since the 2 is in the same position.
Given a permutation of n integers, please help Patrick find the minimum number of special exchanges needed to make the permutation sorted! It can be proved that under given constraints this number doesn’t exceed 1018.
An array a is a subarray of an array b if a can be obtained from b by deletion of several (possibly, zero or all) elements from the beginning and several (possibly, zero or all) elements from the end.
Input
Each test contains multiple test cases. The first line contains the number of test cases t (1≤t≤100). Description of the test cases follows.
The first line of each test case contains integer n (1≤n≤2⋅105) — the length of the given permutation.
The second line of each test case contains n integers a1,a2,…,an (1≤ai≤n) — the initial permutation.
It is guaranteed that the sum of n over all test cases does not exceed 2⋅105.
Output
For each test case, output one integer: the minimum number of special exchanges needed to sort the permutation.
Example input
2 5 1 2 3 4 5 7 3 2 4 5 1 6 7
output
0 2
Note
In the first permutation, it is already sorted so no exchanges are needed.
It can be shown that you need at least 2 exchanges to sort the second permutation.
[3,2,4,5,1,6,7] Perform special exchange on range (1,5)
[4,1,2,3,5,6,7] Perform special exchange on range (1,4)
[1,2,3,4,5,6,7]
テーマ:
tはtグループのサンプルを表し、各グループのデータに対して、まずnは配列内にn個の要素があることを表し、その後、この配列を入力する.区間内のすべての数が元の位置にないように連続する区間を選択することができ、このような操作を少なくとも数回出力することで配列を[1...n]にすることができます.
問題解決の考え方:
まず考えなければならないのは、操作の回数が0 1、2回しかない可能性があり、配列が本来整然としている場合、操作は0回であり、配列の各数字が元の位置にない連続区間が1つしかない場合、1回で並べられ、例えば1、3、4、5が他の場合、まずすべての数が本来の位置にないように1回実行され、もう一度実行すると完全に復元されます.このような元の位置連続区間ではない個数をcntとし,cnt=0であれば本来要求に合致していることを示し,cnt=1であれば1回で並べられた場合,その他の場合は直接cnt=2とし,直接cntを出力すればよい.ACコード:

#include 
#include 
#include 
#include 
#include 
using namespace std;
const int _max = 2e5+50;
int a[_max];
int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        memset(a,0,sizeof a);
        int n;
        cin>>n;
        int cnt=0;
        for(int i=1;i<=n;i++)
        {
            cin>>a[i];
            if(a[i]!=i&&a[i-1]==i-1)//                ，cnt++
              cnt++;
        }
        if(cnt>2)//        2 
          cnt=2;
        cout<<cnt<<endl;
    }
    return 0;
}