(阶段四1.3)UVA 11300 Spreading the Wealth(利用中位数来解决求某一个点到给定的n个点的距离的最小值)

/*
 * UVA_11300.cpp
 *
 *  Created on: 2013年11月17日
 *      Author: Administrator
 */

#include 
  
   
#include 
   
     #include 
    
      #include 
     
       using namespace std; const int maxn = 1000010; long long a[maxn]; long long c[maxn]; long long m; long long sum; long long x ; long long ans; int main(){ int n; while(scanf("%d",&n)!=EOF){ int i; sum = 0; for(i = 1 ; i <= n ; ++i){ scanf("%lld",&a[i]);//初始金币 sum += a[i]; } m = sum/n; c[0] = 0; for(i = 1 ; i < n ; ++i){//求每个人实际给出的金币 c[i] = c[i-1] + a[i] - m; } sort(c,c+n); x = c[n/2]; ans = 0; for(i = 0 ; i < n ;++i){ ans += abs(x - c[i] + 0.0); } printf("%lld\n",ans); // cout<