家庭作业

Description

　　老师在开学第一天就把所有作业都布置了，每个作业如果在规定的时间内交上来的话才有学分。每个作业的截止日期和学分可能是不同的。例如如果一个作业学分为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还有其他方法。 　　你的任务就是找到一个完成作业的顺序获得最大学分。

Input

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

Output

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

Hint

[数据规模]

　　对于所有数据，N<=1000000，作业的完成期限均小于700000。 　　对于部分数据，N<=1000； 　　对于部分数据，N<=10000； 　　对于部分数据，N<=100000； 　　对于部分数据，作业的完成期限小于100； 　　对于部分数据，作业的完成期限小于1000；

题解

看到题目我就突然想起了没有开封的暑假作业wwww

以学分坐关键字降序排序，贪心一下就好了，注意的是对于能否完成当前作业的判断，用一个类似链表的结构记录当前日期之前的最近空闲日期，选的时候找一下就好了

PS:其实程序里面应该是pre而不是nex但是也懒得改了

Code

#include <stdio.h> #include <algorithm> using namespace std; struct homework { int date,value; }; homework t[1101001]; bool d[1001001]; int nex[1001001]; bool cmp(homework a,homework b){return a.value>b.value;} int find(int x) { if (!d[x]) return x; nex[x]=find(nex[x]); return nex[x]; } int main() { int n,ans=0; scanf("%d",&n); for (int i=1;i<=n;i++) { scanf("%d%d",&t[i].date,&t[i].value); nex[i]=i-1; } sort(t+1,t+n+1,cmp); for (int i=1;i<=n;i++) { int tmp=find(t[i].date); if (tmp) { d[tmp]=true; ans+=t[i].value; if (t[i].date!=tmp) nex[t[i].date]=nex[tmp]; } } printf("%d\n",ans); return 0; }