problem link:http://www.spoj.com/problems/LAZYPROG/
How can I solve this problem using priority_queue.I am a newbie in stl.
Pls provide an approach,I am stuck from almost 4 hours.Pls help .
1 Like
Hey there,
Hint 1:
Click to view
The first thing we have to do is make an array of objects containing all 3 parameters of an individual project. Sort the array by ascending deadline, and make a priority queue of pairs. Now we keep track of two things: time and money, both of which are initially set to 0. For each project in the array, we add its initial time to the running total of time, and add a pair (a_i_, b_i_) to the priority queue.
Hint 2:
Click to view
If the running total of time is not greater than the deadline, move onto the next project. Otherwise, pop the pair with greatest a_i off the priority queue. If making the project take 0 time is enough to be back on schedule, pay just enough money to put it back on schedule, decrease the time on the pair, put it back in the priority queue, and move onto the next project. Otherwise, pay the money to make it take 0 time, and move onto the next pair.
I hope this helped you!
EDIT: I ended up coding it in myself, so here is my code for reference. 
Click to view
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <algorithm>
#include <queue>
using namespace std;
struct Triple{
int a, b, c;
Triple(): a(-1), b(-1), c(-1) {}
Triple(int x, int y, int z): a(x), b(y), c(z) {}
bool operator<(Triple const &other) const{ return c < other.c; }
};
int kase, numProjects;
Triple projects [100000];
priority_queue< pair<int, int> > pq;
int main(){
scanf("%d", &kase);
for(int kk = 1; kk <= kase; kk++){
scanf("%d", &numProjects);
for(int i = 0; i < numProjects; i++){
int x, y, z; scanf("%d %d %d", &x, &y, &z);
projects[i] = Triple(x, y, z);
}
sort(projects, projects+numProjects);
int time = 0; double money = 0; pq = priority_queue< pair<int, int> >();
for(int i = 0; i < numProjects; i++){
time += projects[i].b; pq.push(make_pair(projects[i].a, projects[i].b));
if(time <= projects[i].c) continue;
while(true){
pair<int, int> temp = pq.top(); pq.pop();
if(time - temp.second <= projects[i].c){
temp.second -= time-projects[i].c; money += double(time-projects[i].c)/double(temp.first);
time = projects[i].c; pq.push(temp);
break;
}
else{
money += double(temp.second)/double(temp.first); time -= temp.second;
}
}
}
printf("%.2f", money); cout << endl;
}
return 0;
}
1 Like