NYOJ 757 期末考试

　　　　　　　　　　　　　　　　　　　　　　期末考试

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

输入

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

输出

输出扣除的最小分数。

样例输入

样例输出

0
3
5

 1  
 2 #include<cstdio>
 3 #include<queue>
 4 #include<algorithm>
 5 using namespace std;
 6 
 7 struct work
 8 {
 9     int date;
10     int score;
11 };
12 
13 int cmp(work a,work b)
14 {
15     if(a.date==b.date)
16     return a.score<b.score;
17     return a.date<b.date;
18 }
19 
20 int main()
21 {
22     //freopen("in.txt","r",stdin);
23     work a[2005];
24     int i,t,ans;
25     while(scanf("%d",&t)!=EOF)
26     {
27         priority_queue<int,vector<int>,greater<int> >q;
28         for(i=0;i<t;i++)
29         scanf("%d%d",&a[i].date,&a[i].score);
30         sort(a,a+t,cmp);
31         for(ans=0,i=0;i<t;i++)
32         {
33             if(q.size()<a[i].date)
34             q.push(a[i].score);
35             else
36             {
37                 if(a[i].score>q.top())
38                 {
39                     ans+=q.top();
40                     q.pop();
41                     q.push(a[i].score);
42                 }
43                 else
44                 ans+=a[i].score;
45             }
46         }
47         printf("%d
",ans);
48     }
49     return 0;
50 }