家庭作业 纪中2549 贪心+优化

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范围。

分析

我们先把作业按学分从大到小排个序。 用数组f标记第i个时间有没有用过。 然后从第一份作业开始选择做不做。 如果在这一份作业(作业i)的期限之前还有时间可以空闲(f[i]=0)，那就做这一份作业，并且用一个数组标记一下这个时间已经用了(f[i]=1)。 这里可以用一个优化，用一个链表f,f[i]指向f[i]之前的空闲时间，具体见程序

代码

type arr=record x,y:longint; end; var i,j,k:longint; f,fa:array[1..1000010] of longint; a:array[1..1000010] of arr; n:longint; ans:longint; procedure qsort(l,r:longint); var i,j,k:longint; mid:longint; temp:arr; begin if l>=r then exit; i:=l; j:=r; mid:=a[(l+r) div 2].y; repeat while a[i].y>mid do i:=i+1; while a[j].y<mid do j:=j-1; if i<=j then begin temp:=a[i]; a[i]:=a[j]; a[j]:=temp; i:=i+1; j:=j-1; end; until i>j; qsort(l,j); qsort(i,r); end; function find(x:longint):longint;//优化，更新链表 var i,j,k:longint; begin if (x=0) or (f[x]=0) then exit(x); fa[x]:=find(fa[x]); exit(fa[x]); end; begin readln(n); for i:=1 to n do readln(a[i].x,a[i].y); qsort(1,n); ans:=0; for i:=2 to n do fa[i]:=i-1; for i:=1 to n do begin j:=find(a[i].x); if j<>0 then begin f[j]:=1; ans:=ans+a[i].y; end; end; write(ans); end.