NKTARDY - Lập lịch giảm thiểu trễ hạn

Tác giả: RR

Ngôn ngữ: Pascal

{$R+,Q+}
uses math;
const
  FINP='';
  FOUT='';
  MAXN=100011;
var
  f1,f2:text;
  hsize,n:longint;
  ind,dd,h,d,p:array[1..MAXN] of longint;
procedure openF; inline;
begin
  assign(f1,FINP); reset(f1);
  assign(f2,FOUT); rewrite(f2);
end;
procedure closeF; inline;
begin
  close(f1); close(f2);
end;
procedure inp; inline;
var
  i:longint;
begin
  read(f1,n);
  for i:=1 to n do read(f1,p[i]);
  for i:=1 to n do read(f1,d[i]);
  for i:=1 to n do ind[i]:=i;
end;
procedure swap(var a,b:longint); inline;
var
  temp:longint;
begin
  temp:=a; a:=b; b:=temp;
end;
var
  mid:longint;
procedure sort(l,r:longint); inline;
var
  i,j:longint;
begin
  mid:=d[l+random(r-l+1)]; i:=l; j:=r;
  repeat
    while d[i]<mid do inc(i);
    while d[j]>mid do dec(j);
    if i<=j then
      begin
        swap(d[i],d[j]);
        swap(p[i],p[j]);
        swap(ind[i],ind[j]);
        inc(i); dec(j);
      end;
  until i>j;
  if i<r then sort(i,r);
  if l<j then sort(l,j);
end;
procedure ans; inline;
var
  i:longint;
begin
  writeln(f2,n-hsize);
  for i:=1 to n do
    if dd[i]=1 then write(f2,ind[i],' ');
  for i:=1 to n do
    if dd[i]=0 then write(f2,ind[i],' ');
  writeln(f2);
end;
procedure downHeap(i:longint); inline;
var
  j:longint;
begin
  j:=i<<1;
  while (j<=hsize) do
    begin
      if (j<hsize) and (p[h[j+1]]>p[h[j]]) then inc(j);
      if (p[h[j]]>p[h[i]]) then swap(h[i],h[j]);
      i:=j; j:=i<<1;
    end;
end;
procedure upHeap(i:longint); inline;
var
  j:longint;
begin
  j:=i>>1;
  while (i>1) and (p[h[i]]>p[h[j]]) do
    begin
      swap(h[i],h[j]);
      i:=j; j:=i>>1;
    end;
end;
procedure push(u:longint); inline;
begin
  inc(hsize); h[hsize]:=u;
  upHeap(hsize);
end;
procedure pop(var u:longint); inline;
begin
  u:=h[1]; swap(h[1],h[hsize]); dec(hsize);
  downHeap(1);
end;
procedure solve;
var
  i,sum,temp:longint;
begin
  hsize:=0; sum:=0;
  for i:=1 to n do
    if sum+p[i]<=d[i] then
      begin
        sum+=p[i];
        dd[i]:=1;
        push(i);
      end
    else if (hsize>0) and (sum-p[h[1]]+p[i]<=d[i]) and (p[h[1]]>p[i]) then
      begin
        sum+=p[i]-p[h[1]];
        dd[h[1]]:=0;
        pop(temp);
        push(i); dd[i]:=1;
      end;
end;
begin
  openF;
  inp;
  sort(1,n);
  solve;
  ans;
  closeF;
end.

Download