12016번: 라운드 로빈 스케줄러

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


$O(n\lg n)$

작업 수행 시간이 작은 것부터 보면서 진행중인 작업 개수*반복 횟수를 누적한다.
마지막으로 작업을 수행할 때 0번부터 해당 작업 사이 진행할 작업 개수는 bit를 이용해 구한다.

#include<cstdio>
#include<algorithm>
using namespace std;
const int MXN = 1e5;
int bit[MXN + 1], n;
long long r[MXN], c[MXN + 1], s;
int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) scanf("%lld", c + i), c[i] = c[i] * n + i - 1;
    sort(c + 1, c + 1 + n);
    for (int i = 1; i <= n; i++) {
        int h = c[i] % n;
        r[h] = (s += (c[i] / n - c[i - 1] / n)*(n - i + 1)) - n + i + h;
        for (int j = h + 1; j; j -= j&-j) r[h] -= bit[j];
        for (int j = h + 1; j <= n; j += j&-j) bit[j]++;
    }
    for (int i = 0; i < n; i++) printf("%lld\n", r[i]);
    return 0;
}