2012번: 등수 매기기

https://www.acmicpc.net/problem/2012


$O(n\lg n)$

예상 번호를 기준으로 오름차순 정렬하고 각 인덱스를 해당 학생의 등수로 지정한다.

이 방법이 최적임은 증명해보자.
최적해에서 i<j이고 ai>aj인 경우가 존재한다고 가정하면
항상 |ai-i|+|aj-j| >= |ai-j|+|aj-i|이다.
그래서 aj, ai 순으로 등수를 매기면 적어도 이전보다 불만도가 커지지는 않는다.

#include<cstdio>
#include<algorithm>
using namespace std;
int n, a[500001];
long long r;
int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) scanf("%d", a + i);
    sort(a + 1, a + 1 + n);
    for (int i = 1; i <= n; i++) r += abs(a[i] - i);
    printf("%lld", r);
    return 0;
}