在线销售网站设计文献,wordpress 付费主题 时间,网站的关键字 设置,如何推广自己的网站和产品Description 有n个小朋友坐成一圈#xff0c;每人有ai个糖果。每人只能给左右两人传递糖果。每人每次传递一个糖果代价为1。 Input 第一行一个正整数nn1000000#xff0c;表示小朋友的个数#xff0e;接下来n行#xff0c;每行一个整数ai#xff0c;表示第i个小朋友得…Description 有n个小朋友坐成一圈每人有ai个糖果。每人只能给左右两人传递糖果。每人每次传递一个糖果代价为1。 Input 第一行一个正整数nn1000000表示小朋友的个数 接下来n行每行一个整数ai表示第i个小朋友得到的糖果的颗数 Output 求使所有人获得均等糖果的最小代价。 Sample Input 4 1 2 5 4 Sample Output 4 这道题让我想到了白书上面的相似的一道题 UVA11300 Spreading the Wealth A Communist regime is trying to redistribute wealth in a village. They have have decided to sit everyone around a circular table. First, everyone has converted all of their properties to coins of equal value, such that the total number of coins is divisible by the number of people in the village. Finally, each person gives a number of coins to the person on his right and a number coins to the person on his left, such that in the end, everyone has the same number of coins. Given the number of coins of each person, compute the minimum number of coins that must be transferred using this method so that everyone has the same number of coins. Input There is a number of inputs. Each input begins with n (n 1000001), the number of people in the village. n lines follow, giving the number of coins of each person in the village, in counterclockwise order around the table. The total number of coins will fit inside an unsigned 64 bit integer. Output For each input, output the minimum number of coins that must be transferred on a single line. Sample Input 3 100 100 100 4 1 2 5 4 Sample Output 0 4 题意个人围成一圈每个人都有一些硬币每个人只能给左右相邻的人硬币问最少交换几个硬币使每个人硬币一样多。 我第一反应费用流。第二反应费用流。第三反应费用流。 然后看uva11300题解 首先最终每个人金币数量可以计算出来我们用M表示每个人最后拥有的金币数。 我们对于第i个人可以看作他给了他左边的人xi个金币负数表示反向传递他右边的人给了他xi1个金币假设他一开始拥有的金币数量为Ai那么有Ai-xixi1M。 如果我们继续列下去就会变成这样 A1-x1x2M - x2M-A1x1 - 令C1A1-M - x2x1-C1 A2-x2x3M - x3M-A2x22*M-A1-A2x1 - 令C2A1A2-2*M - x3x1-C2 A3-x3x4M - x4M-A3x33*M-A1-A2-A3x1 - 令C3A1A2A3-3*M - x4x1-C3 ....... 那么我们就会得到n个等式但是我们发现我们可以用这n个等式中的任意n-1个去变换得到最后剩下那个等式。 因为我们知道 $\sum A_i M \times n $ 那么最后一个等式Cn0就是x1x1。 也就是说最后那个等式是没有用的我们只会用到n-1个等式。那么这n-1个等式可以用来做什么呢我们怎样才能求得 $ \sum abs(x_i) $ 最小值呢 $ \sum abs( x_i ) abs( x_1 )abs( x_2 )abs( x_3 )......abs( x_n )abs( x_1 ) abs(x_1-C_1) abs(x_1- C_2) ......abs(x_1-C_{n-1})$ 由于Ci是可以直接计算出来的可以当作常数所以说这个等式相当于是求一个最优的x1使得数轴上x1到Ci距离和最小而这个距离和就是我们所求的答案。 最后问题转化成求数轴上一个点到所有已知的点最小距离相信在小学或是初中数学老师都讲过这样的点就是中位数啦。 然后就直接算出C然后算中位数与其他的所有的点的距离。 bzoj1045 代码 //Serene
#includealgorithm
#includeiostream
#includecstring
#includecstdlib
#includecstdio
#includecmath
using namespace std;
const int maxn1e610;
long long n,tot,ans,c,A[maxn],C[maxn];long long aa;char cc;
long long read() {aa0;ccgetchar();while(cc0||cc9) ccgetchar();while(cc0cc9) aaaa*10cc-0,ccgetchar();return aa;
}int main() {nread();for(int i1;in;i) A[i]read(),totA[i];tot/n;for(int i1;in;i) C[i]A[i]-totC[i-1];sort(C1,Cn1);//还有一个C[i]为0的 for(int i1;in;i) ansabs(C[i]-C[(n1)1]);printf(%lld,ans);return 0;
}转载于:https://www.cnblogs.com/Serene-shixinyi/p/7594077.html
