NOT A BLOG | sqybi

SGU 259 — Printed PR

Posted on 五月 12th, 2008.

这题本没啥可说的,一个qsort搞定…l按照从低到高排序就可以…

可是呢…我刚开始竟然没想到…
想了一个KM的算法,就是t和l各作为X,Y结点,另外插入两个空结点.对于左边的第i个结点和右边第k个,如果i<>k,那么他们的边权是max(ti, lk);否则为正无穷.
然后一个KM就求出来了…
这道题的数据范围也够骗人的…100…

{
SGU 259; Printed PR
- sqybi’s code
}
//for my winsty
program sgu259_sqybi;
  const
    nn = 100;

  type
    rec = record
      t, l: longint;
    end;

  var
    n, i, s, t: longint;
    a: array[1..nn]of rec;

  procedure qsort(l, r: longint);
    var
      i, j, d: longint;
      t: rec;
    begin
      if l >= r then exit;
      i := l;
      j := r;
      d := a[(l+r) div 2].l;
      repeat
        while a[i].l > d do inc(i);
        while a[j].l < d do dec(j);
        if i <= j then begin
          t := a[i];
          a[i] := a[j];
          a[j] := t;
          inc(i);
          dec(j);
        end;
      until i > j;
      qsort(l, j);
      qsort(i, r);
    end;

  begin
    readln(n);
    for i:=1 to n do read(a[i].t);
    readln;
    for i:=1 to n do read(a[i].l);
    readln;

    if n <> 1 then qsort(1, n);
    s := 0;
    t := 0;
    for i:=1 to n do begin
      s := s + a[i].t;
      if s + a[i].l > t then t := s + a[i].l;
    end;
    writeln(t);
  end.

阅读(62 次)

Make a Comment

Make A Comment: ( 2 so far )

2 Responses to “SGU 259 — Printed PR”

Comments RSS Feed

Where's The Comment Form?