题目描述
高三一年中的考试多不胜数，并且每次考完之后同学们都会预估一下自己的分数。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可以自动将此分数转化为百分制）。
样例输入
10000
7
4 2 4 3 1 4 6
70 60 50 40 30 20 10
样例输出
9950
题解
先以学分快排，用一条单向链条指向前面空闲的日子，一数组表示各个日子有没有安排作业，从学分最多的开始枚举，判断那一天可不可以做，如果不行往前找一个最近的悠闲的日子。
注意：
1：标记0不能安排作业。
2：记得更新链条。
代码：
vara:array[0..1000,1..2] of longint;b:array[0..1000] of boolean;f:array[0..1000] of longint;n,i,j,ans,sum,c,e:longint;
procedure qsort(l,r:longint);
varmid,p:longint;
begini:=l;j:=r;mid:=a[(l+r)div 2,2];repeatwhile a[i,2]>mid do inc(i);while a[j,2]<mid do dec(j);if i<=j thenbeginp:=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;
beginreadln(e);readln(n);fillchar(f,sizeof(f),false);for i:=1 to n doread(a[i,1]);for i:=1 to n dobegin read(a[i,2]);sum:=sum+a[i,2];end;
end;
function xjhshlr(x:longint):longint;
beginif (f[x]=0)or(b[x]=false) then exit(x);f[x]:=xjhshlr(f[x]);exit(f[x]);
end;
beginassign(input,'exam.in');reset(input);assign(output,'exam.out');rewrite(output);init;qsort(1,n);fillchar(b,sizeof(b),false);b[0]:=true;for i:=1 to n dof[i]:=i-1;for i:=1 to n dobeginif b[a[i,1]]=false then c:=a[i,1]else c:=xjhshlr(f[a[i,1]]);if b[c]=false thenbeginans:=ans+a[i,2];b[c]:=true;end;end;writeln(e-sum+ans);close(input);close(output);
end.