[Codeforces][Round #EDU109][Div.2] B : Permutation Sort (C++)

https://codeforces.com/contest/1525/problem/B

Problem - B - Codeforces

 

[난이도] Div.2
[유형] Greedy

[풀이]
a[1]과 a[N]에 어떤 수가 들어있는지에 따라서 답을 구해야 한다.

최악의 경우는
a[1]에 N, a[N]에 1이 있는 경우, 이 경우에는 1~N-1을 sort -> 2~N을 sorting -> 1~N-1을 sorting 총 3번을 sorting 해야 한다.

이미 정렬이 되어있는 경우 0번

a[1]==1 이거나 a[N]==N인 경우 이것을 제외하고 1번만 정렬하면 되므로 1번

나머지 경우는 2번만 정렬해주면 된다.

 

#include <cstdio>
#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
#include <map>
#include <cmath>
using namespace std;
using ll = long long;
 
int t,N,a[51];
 
int solve(){
    bool ok=1;
    for(int i=1;i<=N;i++){
        if(a[i]!=i){
            ok=0;
            break;
        }
    }
    if(ok) return 0;
    
    if(a[1]==1 || a[N]==N) return 1;
    if(a[1]==N && a[N]==1) return 3;
 
    return 2;
}
 
int main(){
    scanf("%d",&t);
    while(t--){
        scanf("%d",&N);
        for(int i=1;i<=N;i++) scanf("%d",&a[i]);
        printf("%d\n",solve());
    }
}

https://github.com/has2/Problem-Solving/blob/master/codeforces/RoundEDU109-Div.2/B.cpp