Codeforces Round #746 (Div. 2)-B. Hemose Shopping

문제 설명

핫산에게 정수 $n$개로 이루어진 배열이 주어진다. 핫산은 그의 친구 나비한테 이 배열을 오름차순으로 만들어야 한다고 말했다. 하지만 이 뿐이라면 문제가 너무 쉬워지기 때문에 정렬을 할 때 오직 다음 연산만을 사용해야 한다는 제약을 추가했다.

• $1 \le i,j \le n$, $|i - j| \ge x$ 를 만족하는 index $i$와 $j$를 선택하고, 그 다음 $a_i$와 $a_j$의 위치를 바꾼다.

우리가 해야할 것은 나비가 위에서 주어진 연산을 사용해서 배열을 오름차순으로 만들 수 있는지 판별하는 것이다.

Input
첫번째 줄에는 테스트 케이스의 수 $t (1 \le t \le 10^5)$ 이 주어진다.

각 테스트 케이스의 첫번째 줄에는 두 정수 $n$과 $x (2 \le n \le x \le 10^5)$ 가 주어진다.

두번째 줄에는 $n$개 정수 $a_1, a_2, ..., a_n(1 \le a_i \le 10^9)$ 가 주어진다.

Output
각 테스트케이스마다 문자열 1개를 출력해야한다. 이때 "yes"와 "no"는 소문자로 출력하던, 대문자로 출력하던 아무 상관이 없다.

Example
input
4
3 3
3 2 1
4 3
1 2 3 4
5 2
5 1 2 3 4
5 4
1 2 3 4 4

output
NO
YES
YES
YES

문제 접근

사용한 알고리즘: 정렬
걸린 시간 : 00:10
아니 진짜 아이디어는 엄청 간단한 문제인데 왜 이런 문제를 꼬아서 어렵게 생각하는지 모르겠다. 이 증상은 내가 판단했을 때 코드포스 문제를 푸는 양이 부족해서 그런것 같다. 가상 대회를 자주 참여해서 문제를 푸는 절대량을 늘려야지... 장소와 환경이 제한되서 아쉬울 따름이다. 자유로운 곳이였다면 하루에 대회 2번은 참여하고 업솔빙까지 가능했을 것 같은데 정말 아쉽다.

주어진 연산을 잘 보자. 두 index 차이가 $x$보다 작으면 우리는 원소를 바꿀 수 없다. 따라서 이 구간에 위치한 원소는 어떠한 수를 써서라도 건들 수 없기 때문에 이미 정렬되어 있어야 한다. 그리고 이 부분이 키 포인트이자, 문제를 푸는 핵심적인 열쇠이다.

그렇다면 두 index차이가 $x$보다 크거나 같으면 우리는 원소를 자유롭게 바꿀 수 있다는 말이 된다. 우리가 구해야 할 것은 원소를 바꿀 수 없는 구간의 범위를 찾아서 그 부분이 정렬이 되어있으면 우리는 언제든지 정렬을 할 수 있고, 아닌 경우에는 우리는 무슨 수를 써서라도 정렬을 할 수 없다.

한 배열에서 $i = 1$일 때, $|i - j| \ge x$ 를 만족하기 위해서는 $j \le x + 1$ 이어야 한다. 그렇다면 만족 하지 않기 위해서는 $j < x + 1$ 을 만족해야 한다.
한 배열에서 $j = n$ 일 때, $|i - j| \ge x$ 를 만족하기 위해서는 $i \ge n - x$ 이어야 한다. 그렇다면 만족 하지 않기 위해서는 $i > n - x$를 만족해야 한다.
$i$와 $j$의 위치는 자유롭게 바꿀 수 있으므로 $ n - x < k < x + 1$ 를 만족하는 index $k$는 반드시 정렬이 되어 있어야 한다. 그렇기 때문에 이 위치에 있는 index만 이미 정렬되어 있는 원소와 비교를 해서 모두 같으면 "YES" 아니면 "NO"를 출력하면 된다.

정답 코드

#include <iostream>
#include <algorithm>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false); cout.tie(0); cin.tie(0);
    int t; cin >> t;
    while(t--){
        int n, x; cin >> n >> x;
        int arr[n], tmp[n];
        for(int i = 0; i < n; i++){
            cin >> arr[i];
            tmp[i] = arr[i];
        }
        sort(tmp, tmp + n);
        bool flag = true;
        for(int i = n - x; i < x; i++){
            if(arr[i] != tmp[i]){
                flag = false;
                break;
            }
        }
        cout << (flag ? "YES" : "NO") << "\n";
    }
    return 0;
}