티스토리 뷰

문제: icpc.me/12016


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


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


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


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


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


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

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

이 된다.


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


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#include <cstdio>
#include <algorithm>
#define MAX_N 100000
typedef long long ll;
using namespace std;
ll seg[* 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 * + 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&&<= hi)
        return seg[node];
    ll mid = (x + y) >> 1;
    return query(lo, hi, node * 2, x, mid) + query(lo, hi, node * + 1, mid + 1, y);
}
int main() {
    scanf("%lld"&n);
    for (int i = 1; i <= n; i++) {
        update(i, 111, 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, 11, n)*y.first + query(idx + 1, n, 11, n)*(y.first - 1+ v;
        v += y.first;
        update(idx, 011, n);
        r[idx] = res;
    }
    for (int i = 1; i <= n; i++)
        printf("%lld\n", r[i]);
    return 0;
}
cs


'알고리즘 관련 > BOJ' 카테고리의 다른 글

BOJ)9426 중앙값 측정  (7) 2017.01.11
BOJ)5676 음주 코딩  (0) 2017.01.10
BOJ)12016 라운드 로빈 스케줄러  (0) 2017.01.10
BOJ)3653 영화 수집  (0) 2017.01.10
BOJ)6549 히스토그램에서 가장 큰 직사각형  (0) 2017.01.10
BOJ)5419 북서풍  (7) 2017.01.10
댓글
댓글쓰기 폼