acoj-1735給油パイプ【中位数】

タイトルリンク:http://acdream.info/problem?pid=1735
 
ゆそうパイプ
Time Limit: 2000/1000MS (Java/Others) Memory Limit: 262144/131072KB (Java/Others)
Submit  
Statistic  
Next Problem
Problem Description
平面上にはn個の油井があり、現在は1本の幹線線を確立し、すべての油井から生産された原油をすべて輸送するために使用され、幹線はx軸に平行な直線であり、各油井は1本の支線を通じて原油を主幹線に輸送し、現在はn個の油井の平面上の座標を与えている.では、幹線線をどこに建設すれば、すべての支線の全長を最小限に抑えることができるのでしょうか.

Input
まず正の整数n、次にn行の各行の2つの整数は、n個の油井の平面上の位置を表す.nと座標はいずれも1000000以下の正の整数である.
Output
総支線長の最小値を出力し、各結果が1行を占めます.
Sample Input

2

0 0

10 10

Sample Output

10




    ： y    ，            ，         。        ，     ，                       。
  ：

 1 #include <fstream>

 2 #include <iostream>

 3 #include <cstdio>

 4 #include <cmath>

 5 #include <cstdlib>

 6 

 7 using namespace std;

 8 

 9 const int nn=1000005;

10 int a[nn],n,n2,ans;

11 long long cnt;

12 

13 int quick_partition(int i,int j);

14 void quick_sort(int s,int t);

15 

16 int main(){

17     //freopen("D:\\input.in","r",stdin);

18     //freopen("D:\\output.out","w",stdout);

19     while(~scanf("%d",&n)){

20         n2=(n+1)>>1;

21         for(int i=1;i<=n;i++)   scanf("%*d%d",&a[i]);

22         quick_sort(1,n);

23         cnt=0;

24         for(int i=1;i<=n;i++) cnt+=(long long)abs(a[i]-ans);

25         printf("%lld
",cnt);

26     }

27     return 0;

28 }

29 int quick_partition(int i,int j){

30     a[0]=a[i];

31     while(i<j){

32         while(i<j&&a[j]>=a[0])  j--;

33         if(i<j) a[i]=a[j],i++;

34         while(i<j&&a[i]<=a[0])  i++;

35         if(i<j) a[j]=a[i],j--;

36     }

37     a[i]=a[0];

38     return i;

39 }

40 void quick_sort(int s,int t){

41     if(s<t){

42         int tmp=quick_partition(s,t);

43         if(tmp==n2){

44             ans=a[tmp];

45         }else if(tmp<n2){

46             quick_sort(tmp+1,t);

47         }else{

48             quick_sort(s,tmp-1);

49         }

50     }else if(s==t)

51         ans=a[s];

52 }