nyoj757 期末考试 （优先队列）

nyoj757 期末考试 （优先队列）

• 题目757
• 题目信息
• 运行结果
• 本题排行
• 讨论区

期末考试

描述

马上就要考试了，小T有许多作业要做，而且每个老师都给出来了作业要交的期限，如果在规定的期限内没 交作业就会扣期末成绩的分数，假设完成每门功课需要一天的时间，你能帮助小T扣除的分数最小吗？

输入

输入n，表示n门功课(n<2000)，接下来n行，每行两个数a，b，分别表示交作业的最后期限，迟交扣除的分数。
(以文件结尾)

输出

输出扣除的最小分数。

样例输入

3
3 10
3 5
3 1
3
1 6
3 2
1 3
7
1 3
4 2
6 1
4 7
2 6
4 5
3 4

样例输出

0
3
5

上传者

TC_常红立

记得以前做过类似的 就直接敲了

#include <stdio.h>
#include <algorithm>
#include <queue>
using namespace std;
struct node 
{int day,cost;
}c[2005];
bool cmp(node x,node y)
{if(x.day<y.day) return true;if(x.day==y.day&&st&st) return true;return false;
}
int main()
{int n,sum;priority_queue<int,vector<int>,greater<int> >s;while(scanf("%d",&n)!=EOF){while(!s.empty())s.pop();for(int i=0;i<n;i++)scanf("%d %d",&c[i].day,&c[i].cost);sort(c,c+n,cmp);sum=0;for(int i=0;i<n;i++){if(s.size()<c[i].day)//s.size()可以理解为天数。如果当前天数小于最后完成的天数，证明还是有天数空间的，直接入队列s.push(c[i].cost);else//如果当前天数大于最后完成的天数，必须要扣除分数了，为了使得扣除的分数最小，比较s.top()和当前的c[i].cost，舍弃扣除的最小的{int x&#p();if(x<c[i].cost)s.pop(),s.push(c[i].cost),sum+=x;elsesum+=c[i].cost;}}printf("%dn",sum);}return 0;
}