【2016.10.4NOIP普及模拟】Exam

发布于 2019-04-09  9 次阅读


题目描述

三一年中的考试多不胜数,并且每次考完之后同学们都会预估一下自己的分数。
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.
]]>