Hướng dẫn giải của [Free Contest 02] JOB
Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
#include <cstdio>
#include <algorithm>
#include <queue>
using namespace std;
struct JOB
{
long long dead;
long long prof;
bool operator <(const JOB &o) const
{
return dead < o.dead;
}
};
long long N;
JOB job[100001];
int main(void)
{
FILE *inFile = fopen("job.in", "rt");
fscanf(inFile, "%lld", &N);
for(long long i = 0 ; i < N ; i++)
fscanf(inFile, "%lld%lld", &job[i].dead, &job[i].prof);
fclose(inFile);
job[N].dead = 0;
job[N].prof = 0;
N++;
sort(job, job + N);
priority_queue<long long> pq;
long long curTime = 2000000000LL;
long long profit = 0;
for(long long i = N - 1 ; i >= 0 ; i--)
{
while(curTime > job[i].dead && pq.size())
{
curTime--;
profit += pq.top();
pq.pop();
}
curTime = job[i].dead;
pq.push(job[i].prof);
}
FILE *outFile = fopen("job.out", "wt");
fprintf(outFile, "%lld\n", profit);
fclose(outFile);
return 0;
}
Bình luận