BOJ)12016 라운드 로빈 스케줄러

문제: icpc.me/12016

0번 작업부터 N-1번 작업까지 순서대로 수행 할 때 스케줄러는 한 작업을 1초 실행 시킨 뒤 다음 작업으로 넘어간다고 한다.

이 때 각 작업들이 언제 완료 되는지 구하면 된다.

우리는 문제를 풀기위해 쿼리를 전부 받은 뒤 정렬하여 가장 짧은 작업부터 수행해보자.

한 작업을 끝냈을 때 다음작업은 이미 끝난 작업의 완료하는데 필요한 수행시간을 포함한다.

따라서 한 작업이 끝날 때 마다 이미 끝난 작업의 총 수행시간은 따로 더해서 저장할 필요가 있다.

i번째 작업을 할 때 i번째 작업을 완료하는데 필요한 시간을 t라고 하면 

답= (1~i번째 작업중 끝나지 않은 작업의 수)*t+(i+1~N번째 작업중 끝나지 않은 작업의 수)*(t-1) + (이미 끝난 작업의 총 수행시간)  

이 된다.

끝나지 않은 작업의 수는 세그먼트 트리의 부분합을 통하여 쉽게 계산해줄 수 있다.

#include <cstdio>
#include <algorithm>
#define MAX_N 100000
typedef long long ll;
using namespace std;
ll seg[4 * MAX_N], n, x, v;
pair<ll, ll> q[MAX_N + 1];
ll r[MAX_N + 1];
ll update(ll pos, ll val, ll node, ll x, ll y) {
    if (y < pos || pos < x)
        return seg[node];
    if (x == y)
        return seg[node] = val;
    ll mid = (x + y) >> 1;
    return seg[node] = update(pos, val, node * 2, x, mid) + update(pos, val, node * 2 + 1, mid + 1, y);
}
ll query(ll lo, ll hi, ll node, ll x, ll y) {
    if (y < lo || hi < x)
        return 0;
    if (lo <= x&&y <= hi)
        return seg[node];
    ll mid = (x + y) >> 1;
    return query(lo, hi, node * 2, x, mid) + query(lo, hi, node * 2 + 1, mid + 1, y);
}
int main() {
    scanf("%lld", &n);
    for (int i = 1; i <= n; i++) {
        update(i, 1, 1, 1, n);
        scanf("%lld", &x);
        q[i - 1] = { x,i };
    }
    sort(q, q + n);
    for (auto y : q) {
        ll idx = y.second;
        ll res = query(1, idx, 1, 1, n)*y.first + query(idx + 1, n, 1, 1, n)*(y.first - 1) + v;
        v += y.first;
        update(idx, 0, 1, 1, n);
        r[idx] = res;
    }
    for (int i = 1; i <= n; i++)
        printf("%lld\n", r[i]);
    return 0;
}