|
|
|
Problem Description
Link to ACM-ICPC Live Archive (HTML format)
Problem Hints
- Even if it is the usual way to solve some task allocation problems, you should not use dynamic programming for this one.
- The two hints from Hogdson and Moore are almost enough to solve the problem.
Problem Solution
A solution using a quite simple greedy algorithm :
- You read all the input, and sort it with increasing due dates d.
- You initialize some variable called cpd (current processing date) to 0, and a q-indexed priority queue called cpt (current processed tasks) to null.
- Then you analyze every task in the order of increasing due dates :
- If you can process the task according to the cpd and the task parameters, you simply increase cpd by q, and you add the task to cpt.
- If you cannot process the task after having processed cpt, there are two cases :
- if the current task is completed in a shorter time q than the top of cpt (= the task that takes the more time to complete), you pop the top of cpt, push the current task in cpt, and then update cpd with your modifications
- else, you simply discard the current task.
- When you have analyzed all the tasks, you simply count the number of tasks you have actually processed (this can be done during the analysis with some counter).
How to interpret the two hints in the problem description?
- The first one is a clue about the greedy way of solving the problem. Just to process every task one after the other according to some sort is what is suggered.
- The second one can be interpreted in the wrong way if you imagine you will be able to build a sequence by adding all the good Jv after adding a good Ju. The problem is that you don't have a starting point if you create you sequence in this order. A better idea is to take the inverse problem, that is to say if you don't have Jv in the sequence, you can't have Ju. This means that you should always prefer Jv to Ju, which is the basic idea of the algorithm.
As for the complexity of our algorithm, it's O(n log n) with a first quick sort and then at most n insertions in the priority queue. Since n can be very big (maximum is 800.000), a slower algorithm, for example in O(n²), would get a Time Limit Exceeded.
Problem Implementation
Just a little note about this implementation, I know I lose a lot of time using a priority queue for the first sort, but it is the way I implemented it during SWERC'05, and I think it is better to show you the "genuine" code I used to solve the problem :-).
#include <stdio.h>
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
struct tache {
int q,d;
};
class Compare {
public :
int operator()( const struct tache &x, const struct tache &y ) {
return x.d > y.d;
}
};
int main() {
int nbcase,curcase;
int nbtache;
int i,j;
scanf("%d",&nbcase);
for(curcase=0;curcase<nbcase;curcase++) {
int tot,res;
priority_queue<struct tache,vector<struct tache>,Compare> pq;
priority_queue<int> curt;
tot = 0;
res = 0;
scanf("%d",&nbtache);
for(i=0;i<nbtache;i++) {
struct tache blah;
scanf("%d %d",&blah.q,&blah.d);
pq.push(blah);
}
while(!pq.empty()) {
i = pq.top().q;
j = pq.top().d;
if(tot+i <= j) {
tot += i;
curt.push(i);
}
else if(!curt.empty() && i < curt.top()) {
tot -= curt.top();
curt.pop();
res++;
tot += i;
curt.push(i);
}
else {
res++;
}
pq.pop();
}
if(curcase)
printf("\n");
printf("%d\n",nbtache-res);
}
return 0;
}
|
|
|
This wiki