题目描述

三一年中的考试多不胜数，并且每次考完之后同学们都会预估一下自己的分数。
G每次都能把自己的分数预估的很准确，这当然是有诀窍的。
在考试中，首先，G给出一个预期得分，然后将考试分为T个时段(T≤500)，一场考试有很多的小题，G决定每个小题都必须在规定期限ti前完成（1≤ti≤T），如果一道题没能在规定期限前完成，则要从预期得分中扣去一部分分数wi，，wi为自然数，不同的题目分数是不同的。当然，每个题目本身都不是很难，保证在一个时间段内能完成，而且必须从整时段开始。G的得分与如何安排组织自己做题的顺序有很大的关系。G当然希望自己能得到最高的分数，但是时间有限，抽不出时间来安排顺序的G想请你帮她安排做题顺序，算出她能获得的最高分数。

输入

共4行。
第1行为m，表示一开始G的预期得分；
第2行为n，表示有n个题目（1≤n≤T）；
第3行有n个数，分别表示题目1到n的规定完成期限；
第4行有n个数，分别表示题目1到n不能在规定期限前完成的扣分。

输出

仅1行。
表示G能获得的最高分数（假设G可以自动将此分数转化为百分制）。

思路

http://blog.csdn.net/nidhogg__/article/details/52199995
类似于这一题，改改就可以了

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,xx: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,'exam.in'); reset(input);
  assign(output,'exam.out'); rewrite(output);
  readln(m);
  s[0,2]:=1;
  readln(n);
  for i:=1 to n do
    read(a[i,1]);
  readln;
  for i:=1 to n do
    begin
      read(a[i,2]);
      xx:=xx+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(m-xx+ans);
end.