F - Processor
모두 12팀이 맞은 문제로군요.
문제 설명

프로세서가 해야하는 작업의 수 N이 주어지고, i번째 작업은 w[i] 만큼의 작업량을 갖고 있으며 r[i] 시간이 지난 이후에 시작할 수 있고 d[i] 시간이 오기 전에 완료 되어야 합니다. 프로세서의 speed를 s라고 하면 단위 시간당 s만큼의 작업량을 할 수 있는데, 이는 시간마다 달라도 됩니다. 모든 작업을 시간 조건에 맞도록 끝낼 수 있게 하려면, 최대 speed의 최소값은 얼마일까요?
단, 시간을 맞추기 위해 어떤 일을 중간에 끊어서 해도 됩니다. 그리고 그 시간 간격은 단위 시간보다 작을 수도 있습니다(예제 그림).
풀이
언뜻 보면 'deadline이 있는 scheduling problem' 문제로 비교적 널리 알려져 있는 그리디 문제와 유사합니다. 단, 이 문제가 좀 다른 점은 일을 끊어서 할 수 있다는 거죠..
일단 문제의 기본적인 접근은 결정문제입니다. 이분검색으로 답을 정해놓고, 그 답이 맞는가를 확인하는 것이죠. 문제에서 구하는 것은 maximum speed의 최소값이지만 결국 어떤 속도의 상한을 정해놓고, 모든 일을 그 최대 속도로 하는 것이 더 이득이라는 것을 쉽게 알 수 있습니다. 그렇다면 어떤 속도 s로 processing을 했을 때, 끝낼 수 있다면 s를 줄여보고 끝낼 수 없다면 최대 속도 s를 늘려 보면서 검색을 해 보면 되겠습니다.
이제 남은 것은 최대 속도 S가 주어졌을 때, 모든 일들을 deadline에 맞춰서 해낼 수 있는가를 알아내는 것입니다.
이런 종류의 그리디는 제법 유명한데, 기본적인 아이디어는 '현재 내가 할 수 있는 일 중 가장 급한 것부터' 하는 것입니다.
즉, 어떤 시각에서 프로세싱 할 수 있는 작업들이 여러개 있을 텐데(현재 시각이 각 작업의 시작 시각 이상이면), 그 중에서 deadline이 가장 빠른 것부터 처리하는 것입니다. deadline이 가장 빠른 작업을 찾기 위해 heap을 쓸 수 있습니다.
어떤 작업을 쪼개서 할 수 있어야 하는데, 이는 조금만 생각해 보면 그다지 어렵지 않게 해결할 수 있습니다.
어차피 최대 속도가 S라면 1만큼의 일을 하는데 드는 시간 간격이 1/S 이므로, 이 1/S 시간 단위로 각 시간마다 할 수 있는 작업 중 가장 deadline이 임박한 일을 1/S 시간만큼 하면 됩니다. 조금 더 나아가보면, 총 2*N 개의 시각(시작 시간, 종료 시간)이 있는데 이 사이에는 한 종류의 일만 해도 됨(안하거나)을 알 수 있습니다.
시간이 1/S 단위라서 처리가 조금 곤란하다는 문제가 있는데 약간의 트릭을 써서 모든 시각에 속도 S를 곱해버리면 모든 시간이 다 정수가 되겠죠... 그럼 이제 integer (혹은 64bit integer) 자료형을 이용하여 답을 구할 수 있습니다.
요약하면, 미리 모든 작업의 시작과 끝을 시간순으로 정렬해 둔 뒤, 시간을 증가시켜보면서 (마치 plane sweeping 하듯이..) 새롭게 할 수 있는 작업이 생기면 힙에 넣어가면서 각 시간 간격마다 힙에 있는 작업 중 가장 종료 시간이 빠른 작업을 수행합니다. 이런 것을 반복하다가,
아직 작업이 다 끝나지 않았는데 종료 시간이 오는 경우가 존재한다면 불가능한 경우가 됩니다.
그리디 부분의 시간복잡도는 O(N lg N)이 되고, 답의 상한을 X라 했을 때 전체 시간복잡도는 O(N lgN lgX) 가 됩니다.
~~~ cpp

#include
#include
#include
#include
#define maxn 10002
typedef long long ll;
using namespace std;
struct round
{
ll time;
int sign;
int idx;
};
int n;
int r[maxn], d[maxn], w[maxn];
round pro[maxn * 2];
ll remain[maxn], deadline[maxn];
bool operator < (const round &A, const round &B)
{
return A.time < B.time;
}
struct deadline_cmp
{
bool operator () (const int &A, const int &B) {
return deadline[A] > deadline[B];
}
};
bool solve(ll speed)
{
vector xs;
for(int i=1; i<=n; ++i)
{
remain[i] = w[i];
deadline[i] = speed * d[i];
// 시작 시간과 데드라인을 모음
pro[i*2 - 1].time = speed * r[i];
pro[i*2 - 0].time = speed * d[i];
pro[i*2 - 1].sign = 1;
pro[i*2 - 0].sign = -1;
pro[i*2 - 1].idx = pro[i*2].idx = i;
xs.push_back( speed * r[i]);
xs.push_back( speed * d[i]);
}
// 모든 시각을 모아서 소트하고 중복제거
sort(pro + 1, pro + 2*n + 1);
sort(xs.begin(), xs.end());

xs.erase(unique(xs.begin(), xs.end()), xs.end());
// deadline 힙
priority_queue < int, vector, deadline_cmp> heap;
for(int ptr=1, i=0; i < xs.size(); ++i)
{
while(ptr <= 2*n && pro[ptr].time == xs[i])
{
// 새롭게 작업이 추가되었으므로 HEAP으로
if(pro[ptr].sign == 1)
heap.push(pro[ptr++].idx);
// 데드라인을 만났는데 아직 안끝났으면 불가능한 경우!
else if (remain[ pro[ptr++].idx ])
return false;
}
if(i == xs.size() - 1) break;
ll times = xs[i + 1] - xs[i];
while(times > 0 && !heap.empty())
{
// 힙에서 가장 deadline이 임박한 작업을 꺼내서 process
int now = heap.top(); heap.pop();
if(remain[now] <= times)
{
times -= remain[now];
remain[now] = 0;
}
else
{
remain[now] -= times;
times = 0;
heap.push(now);
}
}
}
return true;
}
int main()
{
int T;
for( scanf("%d", &T); T > 0; -- T )
{
scanf("%d", &n);
for(int i=1; i<=n; ++i)
scanf("%d %d %d", r+i, d+i, w+i);
// 이분 검색 부분
ll left = 0, right = 2147483647;
ll mid, answer;
while(left <= right)
{
mid = (left + right) / 2;
if( solve(mid) )
{
answer = mid;
right = mid - 1;
}
else left = mid + 1;
}
printf("%d\n", (int)answer);
}
return 0;
}

<div>[이 글은 과거 홈페이지에서 이전된 글입니다. <a href="http://algospot.andromeda-express.com/zbxe/editorial/54592">원문보기</a>]</div>