Uva 11300 - Spreading the Wealth（中位数距离） - c++编程基础

题目大意：

给出一个整数n 然后n个人的钱。n个人围着一个圆桌

每个人可以给旁边的人钱。最终的目的是所有人的钱一样多。数据保证可以实现。

每有一个人给别人一块钱就是步数加一现在要最少的步数实现。

最终每个人的钱数假设为M=tot/n;

每个人开始有的钱为Ai;

Ci表示Ai-M

这个题就是中位数的距离思想 n个人逆时针标号1-n

首先用x1表示1号给n号的钱的数量

同理x2表示2号给1号的钱

那么我么可以列等式

对于每个人 i Ai-xi+xi+1=M 就是说原来有的钱减去他给钱一个的钱加上后一个给他的钱等于M

我们可以得出 x2 = M-A1+x1 =x1-C1；

x3 = M-A2+x2 = x2-c2 =x1-c1-c2;

.........

我们最终希望的是x1 +x2 +xn的绝对值最小也就是说

|x1| +|x1-c1| + |x1-c1-c2| +.....+|x1-cn-1| 最小

也就是这n个点距离x1 的距离的绝对值最小

要证明的是：给定数轴上的 N 个点，在数轴上的所有点中，中位数离所有定点距离之和最小。凡是能转化成为这个模型的题目都可以用中位数求解，并不知适用于本题。

老外对本题的博客链接：

http://one-problem-a-day.blogspot.com/2011/08/uva-11300-spreading-wealth. html

代码：

#include   
#include   
#include   
#include   
#include   
#include   
#include   
using namespace std;  
  
#define MAXN 1000001  
#define u64 unsigned long long  
#define i64 long long  
#define rep(i,n) for(i=0;i<(n);i++)  
#define min(a,b) (((a)<(b)) (a):(b))  
#define mabs(x) (((x)<0) (-x):(x))  
  
int n;  
u64 a[MAXN];  
i64 A[MAXN];  
u64 sum, per;  
  
int get_random(int a, int b) { //returns a random number between a & b  
 int x = rand();  
 int y = b - a;  
 x = (int)((x / (double)RAND_MAX) * y) + a;  
 if(x < a) x = a;  
 if(x >




 b) x = b;  
 return x;  
}  
  
// partition the array A[p], A[p+1] ... A[r] in such a way so that   
// all the elements left to the pivot element are smaller than it and all the elements right to it are larger than it  
// return the pivot element's index  
int partition(int p, int r) {   
 int x = A[r];  
 int i,j;  
 i = p-1;  
 for(j = p; j < r; j++) {  
  if(A[j] <= x) {  
   i++;  
   swap(A[i], A[j]);  
  }  
 }  
 swap(A[i+1], A[r]);  
 return i+1;  
}  
  
// same functionality as partition(), but selects the pivot element randomly so that no particular input can always expose the O(n^2) worst case behaviour  
int randomized_partition(int p, int r) {  
 int i = get_random(p, r);  
 swap(A[r], A[i]);  
 return partition(p, r);  
}  
  
// select the i-th element largest from the array A[p], A[p+1] ... A[r]  
i64 randomized_select(int p, int r, int i) {  
 if(p == r) return A[p];  
 int q = randomized_partition(p, r);  
 int k = q - p + 1;  
 if(i == k) return A[q];  
 else if(i < k) return randomized_select(p, q-1, i);  
 else return randomized_select(q+1, r, i-k);  
}  
  
  
int main() {  
 int i;  
 u64 res;  
 i64 mid;  
 srand(time(NULL));  
 while(scanf(" %d",&n) == 1) {  
  sum = 0;  
  rep(i,n) {  
   scanf(" %llu",&a[i]);  
   sum += a[i];  
  }  
  per = sum / n;  
  rep(i,n) A[i] = (i64)per - (i64)a[i];  
  for(i=n-2;i>0;i--) A[i] = A[i+1] + A[i];  
  A[0] = 0;  
  //sort(A, A+n);  
  //mid = ( A[n/2] + A[(n-1)/2] ) / 2;  
  mid = randomized_select(0, n-1, n/2 + 1);  
  mid += randomized_select(0, n-1, (n-1)/2 + 1);  
  mid /= 2;  
  res = 0;  
  rep(i,n) {  
   A[i] -= mid;  
   res += mabs(A[i]);  
  }  
  printf("%llu\n",res);  
 }  
 return 0;  
}