信息学奥赛一本通T1430：家庭作业

【题目描述】

老师在开学第一天就把所有作业都布置了，每个作业如果在规定的时间内交上来的话才有学分。每个作业的截止日期和学分可能是不同的。例如如果一个作业学分为10，要求在6天内交，那么要想拿到这10学分，就必须在第6天结束前交。

每个作业的完成时间都是只有一天。例如，假设有7次作业的学分和完成时间如下：

作业号    1    2    3    4    5    6    7
期限    1    1    3    3    2    2    6
学分    6    7    2    1    4    5    1

最多可以获得15学分，其中一个完成作业的次序为2，6，3，1，7，5，4，注意可能d还有其他方法。

你的任务就是找到一个完成作业的顺序获得最大学分。

【输入】

第一行一个整数N，表示作业的数量。

接下来N行，每行包括两个整数，第一个整数表示作业的完成期限，第二个数表示该作业的学分。

【输出】

输出一个整数表示可以获得的最大学分。保证答案不超过longint范围。

【输入样例】

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

【输出样例】

15

【源程序】

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<string>
#include<cstring>
#include<cmath>
#include<ctime>
#include<algorithm>
#include<utility>
#include<stack>
#include<queue>
#include<vector>
#include<set>
#include<map>
#include<bitset>
#define EPS 1e-9
#define PI acos(-1.0)
#define INF 0x3f3f3f3f
#define LL long long
const int MOD = 1E9+7;
const int N = 1000000+5;
const int dx[] = {-1,1,0,0,-1,-1,1,1};
const int dy[] = {0,0,-1,1,-1,1,-1,1};
using namespace std;
struct Node{
    int t,w;
    Node(){}
    Node(int t,int w):t(t),w(w){}
    bool operator < (const Node &rhs)const{
        if(t!=rhs.t)
            return t>rhs.t;
        return w<rhs.w;
    }
}node[N];

priority_queue<pair<int,int> > Q;
int main(){
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%d%d",&node[i].t,&node[i].w);
    sort(node+1,node+1+n);

    int j=1;
    int sum=0;
    for(int i=node[1].t;i>=1;i--){
        while(node[j].t==i&&j<=n){
            Q.push(make_pair(node[j].w,node[j].t));
            j++;
        }
        if(!Q.empty()){
            pair<int,int> temp=Q.top();
            sum+=temp.first;
            Q.pop();
        }
    }

    printf("%d\n",sum);

    return 0;
}

信息学奥赛一本通T1430：贪心算法 家庭作业 归属于 贪心算法，更多同类题解源程序见：贪心算法 和 家庭作业