NOT A BLOG | sqybi

POJ 1990 — MooFest

Posted on 七月 21st, 2008.

好久没大更新了,把最近做的一些题的题解发上来.

_gXX  19:27:46
一群奶牛 = =
_gXX  19:27:51
排成一排
_gXX  19:28:07
但是有点耳聋 = = 所以每个牛都有个听力值
_gXX  19:28:22
他们互相说话的花费就是两个牛的听力值的较大值*距离 = =
_gXX  19:28:29
现在所有牛都要互相说话
_gXX  19:28:31
问 = =
_gXX  19:28:35
要耗费多少啦…

题意大概就是这样,听力值解释为耳聋值更合理一些…

然后呢,按照耳聋值排序,依次处理每一个奶牛.对于排序后的奶牛i,它与1~i-1说话时,较大的一定是i的听力值.这样只需要用i的听力值乘以i与1~i-1所有奶牛的距离和就可以.维护距离可以用树状数组两个,其中一个维护每个坐标上有多少个奶牛,另一个则是存储每个坐标上奶牛个数和坐标值的乘积.
发现我写这东西写得让人看不懂了555…看程序吧.

{
POJ 1990; MooFest
- sqybi’s code
- 树状数组
}
//for my winsty
program pku1990_sqybi;
  const
    nn = 20000;
    xx = 20000;

  type
    TTreeArray = object
      a: array[1..xx]of int64;
      procedure init;
      function lowbit(x: longint): longint;
      procedure add(x, y: longint);
      function sum(x: longint): int64;
    end;
    rec = record
      v, x: int64;
    end;

  var
    a: array[1..nn]of rec;
    t1, t2: TTreeArray;
    s: int64;
    i, n: longint;

  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].v;
      repeat
        while a[i].v < d do inc(i);
        while a[j].v > 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;

  procedure TTreeArray.init;
    begin
      fillchar(a, sizeof(a), 0);
    end;

  function TTreeArray.lowbit(x: longint): longint;
    begin
      lowbit := x and -x;
    end;

  procedure TTreeArray.add(x, y: longint);
    begin
      while x <= xx do begin
        a[x] := a[x] + y;
        x := x + lowbit(x);
      end;
    end;

  function TTreeArray.sum(x: longint): int64;
    var
      s: int64;
    begin
      s := 0;
      while x > 0 do begin
        s := s + a[x];
        x := x - lowbit(x);
      end;
      sum := s;
    end;

  begin
    readln(n);
    for i:=1 to n do readln(a[i].v, a[i].x);
    qsort(1, n);
    s := 0;
    t1.init;
    t2.init;
    t1.add(a[1].x, 1);
    t2.add(a[1].x, a[1].x);
    for i:=2 to n do begin
      s := s + a[i].v * (a[i].x * t1.sum(a[i].x-1) - t2.sum(a[i].x-1))
             + a[i].v * ((t2.sum(xx) - t2.sum(a[i].x)) - a[i].x * (t1.sum(xx)-t1.sum(a[i].x)));
      t1.add(a[i].x, 1);
      t2.add(a[i].x, a[i].x);
    end;
    writeln(s);
  end.

阅读(85 次)

Make a Comment

Make A Comment: ( 4 so far )

4 Responses to “POJ 1990 — MooFest”

Comments RSS Feed

Where's The Comment Form?