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还有其他方法。 你的任务就是找到一个完成作业的顺序获得最大学分。
第一行一个整数N，表示作业的数量。接下来N行，每行包括两个整数，第一个整数表示作业的完成期限，第二个数表示该作业的学分。
Output
输出一个整数表示可以获得的最大学分。保证答案不超过longint范围。
7
1 6
1 7
3 2
3 1
2 4
2 5
6 1
Sample Output
15
【数据规模】
对于所有数据，N<=1000000，作业的完成期限均小于700000。 对于部分数据，N<=1000； 对于部分数据，N<=10000； 对于部分数据，N<=100000； 对于部分数据，作业的完成期限小于100； 对于部分数据，作业的完成期限小于1000；
题解
有一逗逼 http://my.csdn.net/nidhogg__ 建议：
先以学分快排，用一条单向链条指向前面空闲的日子，一数组表示各个日子有没有安排作业，从学分最多的开始枚举，判断那一天可不可以做，如果不行往前找一个最近的悠闲的日子。
注意：
1：标记0不能安排作业。
2：记得更新链条。
代码
var
a:
array[
0..
1000000,
1..
2]
of longint;
b:
array[
0..
1000000]
of boolean;
f:
array[
0..
1000000]
of longint;
n,i,j,ans,c:longint;
procedure qsort(l,r:longint);
var
mid,p:longint;
begin
i:=l;j:=r;
mid:=a[(l+r)
div 2,
2];
repeat
while a[i,
2]>mid
do inc(i);
while a[j,
2]<mid
do dec(j);
if i<=j
then
begin
p:=a[i,
1];a[i,
1]:=a[j,
1];a[j,
1]:=p;
p:=a[i,
2];a[i,
2]:=a[j,
2];a[j,
2]:=p;
inc(i);dec(j);
end;
until i>j;
if l<j
then qsort(l,j);
if i<r
then qsort(i,r);
end;
procedure init;
begin
readln(n);
fillchar(f,sizeof(f),
false);
for i:=
1 to n
do
readln(a[i,
1],a[i,
2]);
end;
function xjhshlr(x:longint):longint;
begin
if (f[x]=
0)
or(b[x]=
false)
then exit(x);
f[x]:=xjhshlr(f[x]);
exit(f[x]);
end;
begin
init;
qsort(
1,n);
fillchar(b,sizeof(b),
false);
b[
0]:=
true;
for i:=
1 to n
do
f[i]:=i-
1;
for i:=
1 to n
do
begin
if b[a[i,
1]]=
false then c:=a[i,
1]
else c:=xjhshlr(f[a[i,
1]]);
if b[c]=
false then
begin
ans:=ans+a[i,
2];
b[c]:=
true;
end;
end;
writeln(ans);
end.
转载请注明原文地址: https://ju.6miu.com/read-1295278.html
