bzoj 3170 manhattan距离

首先将坐标系顺时针旋转45度，得到一个新的坐标系，这个坐标系

对应的坐标的manhattan距离就是原图中的距离，然后快排，利用前缀和

数组O（N）求所有的答案，然后找最小值就行了，总时间O(NlogN)，今天

体力不足，在此不再赘述。。。

/**************************************************************
    Problem: 3170
    User: BLADEVIL
    Language: Pascal
    Result: Accepted
    Time:860 ms
    Memory:19756 kb
****************************************************************/
 
//By BLADEVIL
var
    n                       :int64;
    size                    :array[0..2,0..500010] of int64;
    ans                     :array[0..500010] of int64;
    sum                     :array[0..500010] of int64;
    print                   :int64;
     
function min(a,b:int64):int64;
begin
    if a>b then min:=b else min:=a;
end;
     
procedure swap(var a,b:int64);
var
    c                       :int64;
begin
    c:=a; a:=b; b:=c;
end;
     
procedure init;
var
    i                       :longint;
    x, y                    :int64;
begin
    read(n);
    for i:=1 to n do
    begin
        read(x,y);
        size[1,i]:=x+y;
        size[2,i]:=y-x;
    end;
end;
 
procedure qs(low,high,s:int64);
var
    i, j, xx                :int64;
begin
    i:=low; j:=high; xx:=size[s,(i+j) div 2];
    while i<j do
    begin
        while size[s,i]<xx do inc(i);
        while size[s,j]>xx do dec(j);
        if i<=j then
        begin
            swap(size[1,i],size[1,j]);
            swap(size[2,i],size[2,j]);
            swap(ans[i],ans[j]);
            inc(i); dec(j);
        end;
    end;
    if i<high then qs(i,high,s);
    if j>low then qs(low,j,s);
end;
 
procedure main;
var
    i                       :longint;
begin
    qs(1,n,1);
    for i:=1 to n do sum[i]:=int64(size[1,i]);
    for i:=1 to n do sum[i]:=sum[i]+sum[i-1];
    for i:=1 to n do
        ans[i]:=((i-1)*size[1,i]-sum[i-1])+((sum[n]-sum[i])-(n-i)*size[1,i]);
    qs(1,n,2);
    for i:=1 to n do sum[i]:=int64(size[2,i]);
    for i:=1 to n do sum[i]:=sum[i]+sum[i-1];
    for i:=1 to n do
        ans[i]:=ans[i]+((i-1)*size[2,i]-sum[i-1])+((sum[n]-sum[i])-(n-i)*size[2,i]);
    print:=maxlongint*maxlongint;
    for i:=1 to n do print:=min(print,ans[i]);
    print:=print div 2;
    writeln(print);
end;
 
begin
    init;
    main;
end.

bzoj 3170 manhattan距离

相关推荐