Uva 11300 Spreading the Wealth（贪心）

题目链接：https://vjudge.net/problem/UVA-11300

这道题的思路太神了，但很难想到是贪心。

用M表示每个人最终拥有的金币数。

首先假设有四个人。假设1号给2号3枚，2号又给1号5枚，那么实际上1号并没有给2号，而2号给了1号2枚。这样设$x_2$表示2号给了1号$x_2$枚。若$x_2<0$，那么就表示1号给了2号$-x_2$枚。这样我们就相当于在1号和2号之间连了一条边，表示1号2号之间硬币关系（注意是环形，所以$x_1$表示1号和4号之间的硬币关系）。

假设1号原来有$A_1$枚硬币，那么根据1号给了4号$x_1$枚，收到了$x_2$枚硬币，所以现在1号手中有$A_1+x_2-x_1$枚。根据开始的M，我们可以得到：$M=A_1+x_2-x_1$。同理，我们可以得到其他的方程。

得到n-1个方程之后，可以尝试用$x_1$表示其他的$x_i$：

对于第1个人：$M=A_1+x_2-x_1$ --> $x_2=M-A_1+x_1=x_1-C_1$（规定$C_1=A_1-M_1$）;

对于第2个人：$M=A_2+x_3-x_2$ --> $x_3=M-A_2+x_2=M-A_2+(M-A_1+x_1)=2\times M-A_1-A_2+x_1=x_1-C_2$

.....

然而对于第n个人，这个式子是多余的——关于n的两个x，已在n-1和1中计算了。

现在我们希望所有$x_i$的绝对值要尽可能地小，即$|x_1|+|x_1-C_1|+\cdots +|x_1-C_{n-1}|$的最小，而它的几何意义便是在数轴上找一个点使得这个点到所有C的距离最短。我们会发现这个点便是这些数的中位数（奇偶都是）。

注意一些边界问题..

（详细证明见蓝书P5）

AC代码：

 #include<cstdio>

 #include<iostream>

 #include<cstring>

 #include<cmath>

 #include<algorithm>

 using namespace std;

 const int maxn=;

 int n;

 long long mid,ans,sum,M;

 long long A[maxn],C[maxn];

 inline void init(){

     memset(A,,sizeof(A));

     sum=ans=;

 }

 int main(){

     while(scanf("%d",&n)!=EOF){

         init();

         for(int i=;i<=n;i++){

             scanf("%lld",&A[i]);

             sum+=A[i];

         }

         M=sum/n;

         for(int i=;i<n;i++) C[i]=C[i-]+A[i]-M;

         sort(C,C+n);

         mid=C[n/];

         for(int i=;i<n;i++) ans+=abs(C[i]-mid);

         printf("%lld\n",ans);

     }

     return ;

 }

AC代码

巴特西

Uva 11300 Spreading the Wealth（贪心）

最新文章

热门文章