SSL P2700 老妹的难题

题目大意：
你给你的老妹出了一道题。在N个礼物中找出一个，使之到其他礼物的距离之和最小。由于你老妹还没学开根号，所以我们定义(x1,y1)(x2,y2)两点间的距离为：|x2-x1|+|y2-y1|，为了证明老妹的答案是否是正确的，让你求距离总和的最小值是多少。

30%的数据 N≤100
全部的数据N≤10^5
全部的数据 X i,Yi≤10000

题解：
这题其实不难发现就是把每个点的距离总和求出来然后找一个最小值min，不过直接枚举的话O(N^2)肯定会超时，所以我们考虑一下如何去优化：
我用的是排序+前缀和：
①我们可以将x排序，排序时要将它原本的位置b[i]记录，然后排序后，我们知道这时对于任意一个xj有2种情况：
i>=j 则 它对xi的贡献是xi-xj
j>i 则 它对xi的贡献是xj-xi
这时候我们发现xi对ans[b[i]]的总贡献是：
（i*xi-∑x[1..i]）+（∑x[i+1..n]-(n-i)*xi）
然后求一段连续的区间的总和，我们可以用前缀和O(N)去跑一遍，然后直接O(1)求
然后我们对Y进行同样的操作，最后得出来的ans[i]，在里面找一个min。

时间复杂度：O(N)

var
    sum,ans,a,b,c,d:array [0..100001] of longint;
    i,j,n,min:longint;

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

procedure js;
var
     i:longint;
begin
   for i:=1 to n do sum[i]:=sum[i-1]+a[i];
   for i:=1 to n do
       ans[b[i]]:=ans[b[i]]+(a[i]*i-sum[i])+((sum[n]-sum[i])-(n-i)*a[i]);
end;
begin
     assign(input,'sister.in'); reset(input);
     assign(output,'sister.out');rewrite(output);
     readln(n);
     for i:=1 to n do
     begin
          readln(a[i],c[i]);
          b[i]:=i; d[i]:=i;
     end;
     qsort(1,n); js;
     a:=c; b:=d;
     qsort(1,n); js;
     min:=maxlongint;
     for i:=1 to n do
       if min>ans[i] then min:=ans[i];
     writeln(min);
     close(input); close(output);
end.