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

문제 링크 : [백준] 라운드 로빈 스케줄러(12016)

문제 설명

CPU에 작업 여러개가 실행 중일 때, Round robin 형태(1초씩)로 스케줄링이 될 때, 각 작업이 종료되는 시간을 구하시오.

입력

N(작업의 갯수, 1<=N<=100,000)
D₁ D₂ ...D_n(각 작업에 걸리는 시간,1<=D_i<=1,000,000,000)

4
2 1 2 4

출력

5
2
6
9

카테고리

#세그먼트 트리, #펜윅 트리, #우선 순위 큐

시간 복잡도 상한

작업의 갯수가 10만개 이므로, N²이 되면 타임아웃이 됩니다.
최대 O(N*logN) 에 풀어야 합니다.

해결 방법

1. 한 싸이클씩 매번 돌리면 되지만, 그럴 경우, 작업에 걸리는 시간이 1억이면 타임아웃이 납니다.
2. 남은 작업 중 최소시간만큼은 반드시 종료되는 작업 없이 반복이 진행됩니다.
3. 남은 작업 중 최소시간(min_sec)만큼 반복 된다면, 최소시간을 가진 작업이 종료됩니다.
   3-1. 종료된 작업에 걸린 시간은 아래와 같습니다.

   min_sec*남아있던 작업의 갯수-종료된 작업보다 뒤에 있는 작업의 갯수

4. 최소 작업 시간을 가진 작업을 찾는 것은 Priority Queue를 이용하여 찾습니다.(최소 작업 시간이 같을 경우, index가 앞선 것으로 찾습니다.)
5. 최소 작업 시간보다 뒤에 있는 작업의 갯수는 Fenwick tree를 이용하여 찾습니다.
6. 남아있던 작업의 갯수는 Priority Queue의 사이즈와 같습니다.
7. 4, 5, 6을 가지고 각 작업이 종료되는 시간을 구합니다.

코드

#include<iostream>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std;
typedef long long L;
typedef pair<L,int>P;
int n,t[100000],i;
priority_queue<P,vector<P>,greater<P>>z;
L a[100001],p,b,x,y;
void u(int p,int v){
    while(p<=n)t[p]+=v,p+=p&-p;
}
void init(){
    for(int p=1;p<=n;p++)u(p,1);
}
int q(int p){
    int s=0;
    while(p)s+=t[p],p-=p&-p;
    return s;
}
int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin>>n;
    for(i=1;i<=n;i++)cin>>p,z.push({p,i});
    init();
    for(p=i=0;i<n;i++){
        P c=z.top();z.pop();
        x=q(n);
        y=q(c.second);
        if(b!=c.first)p+=x*(c.first-b),b=c.first;
        a[c.second]=p-x+y;
        u(c.second,-1);
    }
    for(i=1;i<=n;i++)cout<<a[i]<<"\n";
}