正文

[haoi2008]糖果传递

NaVi_Awson  NaVi_Awson  2022-09-24  352

关键词：

Description

有n个小朋友坐成一圈，每人有ai个糖果。每人只能给左右两人传递糖果。每人每次传递一个糖果代价为1。

Input

第一行一个正整数nn<=1'000'000，表示小朋友的个数．

接下来n行，每行一个整数ai，表示第i个小朋友得到的糖果的颗数．

Output

求使所有人获得均等糖果的最小代价。

Sample Input

4
1
2
5
4

Sample Output

题解

咳咳...[UVa 11300]Spreading the Wealth

 1 //It is made by Awson on 2017.10.23
 2 #include <set>
 3 #include <map>
 4 #include <cmath>
 5 #include <ctime>
 6 #include <cmath>
 7 #include <stack>
 8 #include <queue>
 9 #include <vector>
10 #include <string>
11 #include <cstdio>
12 #include <cstdlib>
13 #include <cstring>
14 #include <iostream>
15 #include <algorithm>
16 #define LL long long
17 #define Min(a, b) ((a) < (b) ? (a) : (b))
18 #define Max(a, b) ((a) > (b) ? (a) : (b))
19 #define sqr(x) ((x)*(x))
20 #define Abs(a) ((a) < 0 ? (-(a)) : (a)) 
21 using namespace std;
22 const int N = 1000000;
23 
24 LL n, a[N+5], m;
25 
26 void work() {
27   scanf("%lld", &n);
28   for (int i = 1; i <= n; i++) {
29     scanf("%lld", &a[i]); m += a[i];
30   }
31   m /= n;
32   for (int i = 1; i <= n; i++) {
33     a[i] = a[i-1]+a[i]-m;
34   }
35   sort(a+1, a+n+1);
36   LL mid = a[n>>1], ans = 0;
37   for (int i = 1; i <= n; i++) ans += Abs(mid-a[i]);
38   printf("%lld\n", ans);
39 }
40 int main() {
41   work();
42   return 0;
43 }

[haoi2008]糖果传递

Description有n个小朋友坐成一圈，每人有ai个糖果。每人只能给左右两人传递糖果。每人每次传递一个糖果代价为1。Input第一行一个正整数nn<=1‘000‘000，表示小朋友的个数．接下来n行，每行一个整数ai，表示第i个小朋友得到的... 查看详情

bzoj1045:[haoi2008]糖果传递(数论)

1045:[HAOI2008]糖果传递题目：传送门（双倍经验3293）题解：　　一开始想着DP贪心一顿乱搞，结果就GG了十分感谢hzwer大佬写的毒瘤数论题解：　　首先，最终每个小朋友的糖果数量可以计算出来，等于糖果... 查看详情

p2512[haoi2008]糖果传递(代码片段)

P2512[HAOI2008]糖果传递题目描述有n个小朋友坐成一圈，每人有ai个糖果。每人只能给左右两人传递糖果。每人每次传递一个糖果代价为1。输入输出格式输入格式：小朋友个数n下面n行ai输出格式：求使所有人获得均等糖果的最小代... 查看详情

bzoj1045[haoi2008]糖果传递

环形均分纸牌问题。用A[i]表示糖果数，sum表示目标的糖果数量。用X[i]表示从i+1移动到i的糖果的个数（可+可-）。由此可以得到式子A[i]+X[i]-X[i-1]=sum。我们可以得到这样的n-1个方程（第n个可以由前n-1个推导）。但是这样不足以求... 查看详情

[haoi2008]糖果传递(代码片段)

题目描述有n个小朋友坐成一圈，每人有ai个糖果。每人只能给左右两人传递糖果。每人每次传递一个糖果代价为1。输入输出格式输入格式：小朋友个数n下面n行ai输出格式：求使所有人获得均等糖果的最小代价。输入输出样例输... 查看详情

haoi2008糖果传递-贪心(代码片段)

Description　　有n个小朋友坐成一圈，每人有ai个糖果。每人只能给左右两人传递糖果。每人每次传递一个糖果代价为1。求使所有人获得均等糖果的最小代价。Input　　小朋友个数n，下面n行aiSampleInput41254SampleOutput4思思维难度高的... 查看详情

贪心bzoj1045:[haoi2008]糖果传递(代码片段)

...贪心思考过程Description有n个小朋友坐成一圈，每人有ai个糖果。每人只能给左右两人传递糖果。每人每次传递一个糖果代价为1。Input第一行一个正整数nn<=1‘000‘000，表示小朋友的个数．接下来n行，每行一个整数ai，表示第i个... 查看详情

p2512[haoi2008]糖果传递(代码片段)

p2512[haoi2008]糖果传递题解数学(代码片段)

　　题目描述有n个小朋友坐成一圈，每人有ai个糖果。每人只能给左右两人传递糖果。每人每次传递一个糖果代价为1。输入输出格式输入格式：小朋友个数n下面n行ai 输出格式：求使所有人获得均等糖果的最小代价... 查看详情

bzoj-1045-[haoi2008]糖果传递（中位数原理）

[bzoj1045][洛谷p2512][haoi2008]糖果传递

bzoj1045[haoi2008]糖果传递

传送门很久以前写过的题，忘得一干二净。题解//Twenty#include<cstdio>#include<cstdlib>#include<iostream>#include<algorithm>#include<cmath>#include<cstring>#include<queue>#include< 查看详情

bzoj1045[haoi2008]糖果传递

...意【题解】思路来自hzwer..设xi表示第i个人往左传递了xi个糖果。(如果小于0表示旁边的人给他了糖果。则ans=∑|xi|最后所有人的糖果数都变成sum/n->avg则a1-x1+x2=avga2-x2+x3=avg...然后可以用avg和x1来表示所有的x2...xn比如x2=x1-(avg-a1)x3=x1... 查看详情

haoi2008糖果传递(代码片段)

...但是其实我们不需要再枚举断点。首先每个人最后分到的糖果数是固定的，我们设x[i]表示第i个人给了ta左边的人多少颗糖果（第一个人就给到最后一个人），a[i]表示小朋友原来有多少糖果。那么就有a[i]-x[i]+x[i+1]=ave，也就得到... 查看详情

p2512[haoi2008]糖果传递(代码片段)

...想看也可以直接看结论）首先如果要让每个人最终的糖果一样多1.那么肯定最终每个人的糖果数量为每个人糖果数量的平均数..(显然...)还有一个显然的结论：2.如果a把糖分给别人，那么a就不应该再收到糖不然就不可能是最... 查看详情

[haoi2008]糖果传递(代码片段)

嘟嘟嘟规定第i个人只给第i-1个人糖果，为xi个，因为若xi<0，说明第i-1个人给第i个人|xi|个。那么ans=|x1|+|x2|+|x3|+……+|xn|那么就可以列出：a1-x1+x2=ave,a2-x2+x3=ave,a3-x3+x4=ave……,an-xn+x1=ave。因为从前n-1个方程可以推导出第n个方... 查看详情

[bzoj1045][haoi2008]糖果传递数学

...像，想一想很容易理解。设最后每个小朋友能得到$ave$个糖果，所以有$a[i]+x[i]-x[i+1]=ave$。写出每一个形如这样的式子，可以消元得到$x[n]=x[1]+(n-1)*ave 查看详情

bzoj1045[haoi2008]糖果传递排序(代码片段)

题面题目传送门解法环形均分纸牌和这道题是一模一样的时间复杂度：(O(nlog))代码#include<bits/stdc++.h>#defineintlonglong#defineN1000010usingnamespacestd;template<typenamenode>voidchkmax(node&x,nodey)x=max(x,y);temp 查看详情