题目描述

老师在开学第一天就把所有作业都布置了，每个作业如果在规定的时间内交上来的话才有学分。每个作业的截止日期和学分可能是不同的。例如如果一个作业学分为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

思路

。。。我也不知道怎么讲详情请看 http://my.csdn.net/a_loud_name（ 某三班同学的博客）
但是我还是来尝试解释一下，首先按照学分从大到小排序，然后开一个数组s，s[i,2]来记录这个时间是不是被占用了，s[i,1]开始是指向前一位的指针
每次取学分最大的值放入距离其结束时间最近的地方，这时就要用到递归来寻找最近的空闲时间点然后在递归的过程中将所有已经占用的点的指针全部转移到找到的空闲点的指针指的位置上，然后如果找到了第0位是就说明放不下了，直接跳过当前任务，进行下一个，所以在开始时要将s[0,2]赋为1，这样就直接跳过了，一直做到全部做完为止每找到一个可以做的就直接ans+1就可以了

var
  a:array[0..1000000,1..2] of longint;
  s:array[0..1000000,1..2] of longint;
  i,j,k,n,m,x,y,max,ans:longint;
procedure sort(l,r:longint);
var
  i,j,mid,t:longint;
begin
  i:=l; j:=r;
  mid:=a[(r+l) div 2,2];
  repeat
    while a[i,2]>mid do inc(i);
    while a[j,2]j;
  if il then sort(l,j);
end;

function find(x:longint):longint;
begin
  if (s[x,1]=0) or (s[x,2]=0) then exit(x);
  s[x,1]:=find(s[x,1]);
  exit(s[x,1])
end;

begin
  assign(input,'10.in');
  reset(input);
  s[0,2]:=1;
  readln(n);
  for i:=1 to n do
    begin
      readln(a[i,1],a[i,2]);
    end;
  sort(1,n);

  for i:=1 to n do
    s[i,1]:=i-1;

  for i:=1 to n do
    begin
      if s[a[i,1],2]=0 then x:=a[i,1]
      else
      x:=find(s[a[i,1],1]);
      if s[x,2]=0 then
       begin
         s[x,2]:=1;
         ans:=ans+a[i,2];
        end;
    end;
  writeln(ans);
  close(input);
end.