【CF732D】Exams（线性扫描，贪心，二分）

题意：有m门需要过的课程，n天的时间可以选择复习、考试（如果的d[i]为0则只能复习），一门课至少要复习a[i]天才能通过（可以不连续的复习得到a[i]），问最早什么时候可以把所有课程都通过，如果不能输出-1。

1 ≤ n, m ≤ 10^5) 

思路：贪心思想可知每门课尽可能拖到最后考是最优方案，这样复习的天数就最多

        二分答案验证是否可行，每考一门课就把复习的总日数减去

var a,b,c,d:array[1..110000]of longint;
    n,m,l,r,mid,last,i:longint;

function isok(len:longint):boolean;
var i,s:longint;
begin
 fillchar(b,sizeof(b),0);
 fillchar(c,sizeof(c),0);
 for i:=len downto 1 do
  if (a[i]>0)and(c[a[i]]=0) then
  begin
   b[i]:=a[i];
   c[a[i]]:=1;
  end;
 s:=0;
 for i:=1 to len do
  if b[i]=0 then inc(s)
   else
   begin
    if d[b[i]]>s then exit(false)
     else s:=s-d[b[i]];
   end;
 for i:=1 to m do
  if c[i]=0 then exit(false);
 exit(true);
end;

begin
 //assign(input,'cf732D.in'); reset(input);
 //assign(output,'cf732D.out'); rewrite(output);
 readln(n,m);
 for i:=1 to n do read(a[i]);
 for i:=1 to m do read(d[i]);
 l:=1; r:=n; last:=n+1;
 while l<=r do
 begin
  mid:=(l+r)>>1;
  if isok(mid) then begin last:=mid; r:=mid-1; end
   else l:=mid+1;
 end;
 if last=n+1 then writeln(-1)
  else writeln(last);
 //close(input);
 //close(output);
end.