451-B, *1300

Problem - 451B - Codeforces

문제

• 크기가 $n(1 \leq n \leq 10^{5})$인 배열이 주어진다
• 오직 한번만 배열의 일정 구간을 뒤집어서 배열을 오름차순으로 정렬할 수 있는가?

 

$O(n)$

문제의 상황을 감소하는 구간의 개수에 따라 나눠보자
(감소하는 구간 $[l,\ r]$이란 구간 내에서 감소하면서 $\mathrm{arr[l-1] < arr[l]\ and\ arr[r] < arr[r+1]}$을 만족)

i) 감소구간이 0개
배열이 오른차순으로 정렬되어 있다는 의미

ii) 감소구간이 1개
감소구간을 뒤집으면 오름차순이 될 수도 있음

iii) 감소구간이 2개 이상
배열이 오름차순이 될 수 없다

#include <bits/stdc++.h>
#define endl "\n"
using namespace std;
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
 
    int n;
    cin >> n;
    vector<int> v;
    int tmp;
    for(int i = 0; i < n; i++){
        cin >> tmp;
        v.emplace_back(tmp);
    }
 
    if(n==1){
        cout << "yes" << endl;
        cout << 1 << ' ' << 1 << endl;
        return 0;
    }
 
    vector<pair<int, int> > des;
    int front = 0;
    bool isdescending = false;
    for(int i = 0; i < n-1; i++){
        if(v[i] < v[i+1] && isdescending){
            des.emplace_back(front, i);
            isdescending = false;
        }
        if(v[i] > v[i+1] && !isdescending){
            front = i;
            isdescending = true;
        }
    }
    if(isdescending) des.emplace_back(front, n-1);
 
    if(des.size() == 0){
        cout << "yes" << endl;
        cout << 1 << ' ' << 1 << endl;
    }
    else if(des.size() == 1){
        int f_ind = des.front().second;
        int t_ind = des.front().first;
        if(t_ind > 0 && v[t_ind-1] > v[f_ind] || f_ind < n-1 && v[t_ind] > v[f_ind+1]) cout << "no" << endl;
        else{
            cout << "yes" << endl;
            cout << t_ind+1 << ' ' << f_ind+1 << endl;
        }
    }
    else cout << "no" << endl;
 
    return 0;
}cs

 

$O(nlog\ n)$

이번 풀이에서는 배열의 원소를 상대적인 크기로 치환하여 다룬다
즉, 가장 작은 원소를 0, 가장 큰 원소를 n-1 로 치환한다

그러면, 오름차순으로 정렬된 배열은 다음과 같다
$$\mathrm{Ord}=[0,\ 1,\ ...\ ,\ n-1]$$

한편, 오직 한번만 배열의 일정 구간을 뒤집어서 오름차순으로 정렬되는($\mathrm{Ord}$와 같아지는) 배열은
$\mathrm{Ord}$의 일정 구간을 뒤집어서 만들어지는 배열 집합($S$)의 원소이다

$S$의 원소 $A$가 감소하는 구간$[l, r]$이 있다면
$$A[i] \neq i$$
을 만족하는 최소 $i$가 $l$, 최대 $i$가 $r$ 이다

따라서 준 배열이 $l$과 $r$을 찾아서 뒤집어 본 다음 $\mathrm{Ord}$와 같아지면 yes, 아니면 no

#include <bits/stdc++.h>
#define endl "\n"
using namespace std;
 
int n;
int a[100001];
int b[100001];
map<int, int> m;
 
void Substitue()
{
    for(int i = 0; i < n; i++) b[i] = a[i];
    sort(b, b+n);
    for(int i = 0; i < n; i++) m[b[i]] = i;
    for(int i = 0; i < n; i++) a[i] = m[a[i]];
}
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
 
    cin >> n;
    for(int i = 0; i < n; i++) cin >> a[i];
 
    Substitue();
 
    int l = -1;
    for(int i = 0; i < n; i++){
        if(a[i] != i){
            l = i;
            break;
        }
    }
 
    int r = -1;
    for(int i = n-1; i >= 0; i--){
        if(a[i] != i){
            r = i;
            break;
        }
    }
 
    if(l == -1) {
        cout << "yes" << endl;
        cout << 1 << ' ' << 1 << endl;
    }
    else{
        reverse(a+l, a+r+1);
        bool isOrdered = true;
        for(int i = 0; i < n; i++){
            if(a[i] != i){
                isOrdered = false;
                break;
            }
        }
        if(isOrdered) {
            cout << "yes" << endl;
            cout << l+1 << ' ' << r+1 << endl;
        }
        else cout << "no" << endl;
    }
 
    return 0;
}cs