期末考试
时间限制：1000 ms | 内存限制：65535 KB
难度：2
描述
马上就要考试了，小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
题目分析：此题的关键是要对数据先排一下序，怎么排问题就来了，
此问题是让尽可能的少扣分，那么就应该按时间来排了，时间短的要尽快做了，但是有可能时间短的分值很低，也不能为了做时间短的而把分值高的给放弃。所以要先按时间排序，时间相等的就按分值排序，都是从小到大排。
排完序就用队列来解决取舍问题，队首存的都是分值最高的科目，队里存的都是做过的科目。
#include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #include<queue> using namespace std; struct qu { int t; int s; }a[2001]; bool cmp(qu x,qu y) { if(x.t!=y.t) return x.t<y.t; return x.s<y.s; }; int main() { int n; priority_queue<int,vector<int>,greater<int> >q; while(cin>>n) { while(!q.empty()) q.pop(); int i; for(i=0;i<n;i++) cin>>a[i].t>>a[i].s; sort(a,a+n,cmp); int cost=0; for(i=0;i<n;i++) { if(q.size()<a[i].t) // 如果队列长度(长度就是天数，你存一个就要花一天的时间做，当长度大于或等于科目的期限的化此科目就又被放弃的可能，但是不一定被放弃，看下边。 q.push(a[i].s); else { if(q.top()<a[i].s)// 如果这可科目的分值比队首的分值大那么就把队首的科目放弃，接着清除队首存入这个险些被放弃的科目，依次进行(来解决取舍问题） { cost+=q.top(); q.pop(); q.push(a[i].s); } else cost+=a[i].s; } } cout<<cost<<endl; } return 0; }
