NYOJ-757-期末考试

期末考试
时间限制：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;
}