[백준] 12016 라운드 로빈 스케줄러

 각 작업을 1번부터 N번까지 한번에 1초씩 실행시킬 때, 각 작업이 언제 완료되는지 구하는 문제다.

이 문제는 작업의 양이 적은 순으로 보면 된다. 직접 써보면 규칙을 찾을 수 있다.

총 걸린 시간 - 내 뒤에 남은 작업을 하면 내가 끝나는 시간을 알 수 있다..!

이 때 총 걸린 시간은 

if(현재 작업 시간 != 이전 작업 시간)

==> 이전에 총 걸린 시간 + 남은 작업*(현재 작업의시간 - 이전 작업의 시간)이다

이것만 안다면 인덱스 트리로 문제를 풀 수있다..!

소스코드

#include <iostream>
#include <algorithm>
using namespace std;
#define ll long long
#define MAXN 100010
ll tree[MAXN], ans[MAXN], n;
pair<ll, ll> arr[MAXN];
ll sum(int x) {
    ll ret = 0;
    for (int i = x; i > 0; i -= (i&-i)) ret += tree[i];
    return ret;
}
void update(int x,ll val) {
    for (int i = x; i <= n; i += (i&-i)) tree[i] += val;
}
int main() {
    scanf(" %lld", &n);
    for (int i = 1; i <= n; i++) {
        ll x; scanf(" %lld", &x);
        update(i,(ll)1);
        arr[i] = { x,(ll)i };
    }
    sort(arr + 1, arr + n + 1);
    ll tsum = 0, prev = 0, pos = 0;
    for (int i = 1; i <= n; i++) {
        pos = arr[i].first;
        if(prev != pos)     tsum += sum(n)*(pos - prev);
        ans[arr[i].second] = tsum - (sum(n) - sum(arr[i].second));
        update(arr[i].second,-1);
        prev = pos;
    }
    for (int i = 1; i <= n; i++) printf("%lld\n", ans[i]);
}