[BOJ 2517] 달리기

문제 출처 : https://www.acmicpc.net/problem/2517

 

풀이 :

 

분할정복으로 풀 수 있는 문제입니다.

머지소트를 진행하면서 왼쪽보다 오른쪽이 더 클때 순위를 왼쪽의 남은 숫자 만큼 빼주시면 됩니다.

원리는 우측에 있는 러너가 좌측으로 이동할때 좌측에 남은 숫자만큼 추월을 한다고 생각하시면 됩니다.

 

#include<stdio.h>
 
struct num {
    int v, r;
    num(int v, int r) :v(v), r(r) {}
    num() {}
};
int n, t, rank[500000];
num arr[500000], sort[500000];
 
void mergesort(int l, int r) {
    if (l >= r)return;
    int mid = (l + r + 1) / 2;
    int ll = l, rr = mid, cnt = l;
    while (ll < mid&&rr <= r) {
        if (arr[ll].v > arr[rr].v) {
            sort[cnt++] = arr[ll++];
        }
        else {
            sort[cnt++] = arr[rr];
           rank[arr[rr++].r] -= mid-ll;
        }
    }
    while (ll < mid)sort[cnt++] = arr[ll++];
    while (rr <= r)sort[cnt++] = arr[rr++];
    for (int i = l; i <= r; i++)arr[i] = sort[i];
}
 
void merge(int l, int r) {
    if (l >= r) return;
    int mid = (l + r + 1) / 2;
    merge(l, mid - 1);
    merge(mid, r);
    mergesort(l, r);
}
 
int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf("%d", &t);
        arr[i] = num(t, i);
        rank[i] = i;
    }
    merge(0, n - 1);
    for (int i = 0; i < n; i++)printf("%d\n", rank[i]+1);
}