1758번: 알바생 강호

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


$O(n\lg n)$

차감이 되는 양을 최소로 해야 하기 때문에 작은 팁일 수록 큰 등수에 배치하면 된다.

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