正文

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

hbyer  hbyer  2023-03-09  237

关键词：

Description

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

Input

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

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

Output

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

Sample Input

Sample Output

Solution

设(x_i)表示第(i)个人给了第(i-1)个人多少，负数表示反着给，(x_1)表示(1)号给(n)号。

设(s=sum_i=1^na_i/n)，即平均数。

所以显然可以得到一系列等式：
[ s=a_1-x_1+x_2s=a_2-x_2+x_3\vdots s=a_n-x_n+x_1 ]
但是注意到最后一个可以被前面的推出来，所以不能解出(x)，可以考虑用(x_1)表示剩下的(x)，得：
[ x_2=s-a_1+x_1x_3=2s-a_1-a_2+x_1\vdotsx_n=a_n-s+x_1=(n-1)s-sum_i=1^n-1a_i+x_1 ]
然后可以发现前面那一块可以(O(n))算出来，设为(c_i)，那么问题就转化为了最小化：
[ f(x)=sum_i=1^n|c_i-x| ]
这个可以看成一维数轴上一个点和一堆确定的点的距离和，取中点就好了。

#include<bits/stdc++.h>
using namespace std;

#define int long long 
 
void read(int &x) 
    x=0;int f=1;char ch=getchar();
    for(;!isdigit(ch);ch=getchar()) if(ch=='-') f=-f;
    for(;isdigit(ch);ch=getchar()) x=x*10+ch-'0';x*=f;

 
void print(int x) 
    if(x<0) putchar('-'),x=-x;
    if(!x) return ;print(x/10),putchar(x%10+48);

void write(int x) if(!x) putchar('0');else print(x);putchar('
');

const int maxn = 1e6+10;

int n,a[maxn],c[maxn],ans;

signed main() 
    read(n);int sum=0;
    for(int i=1;i<=n;i++) read(a[i]),sum+=a[i];sum/=n;
    for(int i=2;i<=n;i++) c[i]=c[i-1]+sum-a[i-1];
    int mid=(n+1)>>1;nth_element(c+1,c+mid,c+n+1);
    for(int i=1;i<=n;i++) ans+=abs(c[mid]-c[i]);write(ans);
    return 0;

bzoj1045[haoi2008]糖果传递

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

bzoj1045[haoi2008]糖果传递

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

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

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

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

题目：https://www.lydsy.com/JudgeOnline/problem.php?id=1045好像是贪心...但这是一个环...看博客：http://hzwer.com/2656.html真是神奇的构造...还是应该大胆地先把各种变量都设出来再处理。代码如下：#include<iostream>#include<cstdio>#include<c... 查看详情

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... 查看详情

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

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

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

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

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

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

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

bzoj1045:[haoi2008]糖果传递&&bzoj3293:[cqoi2011]分金币

...是绝望的。。首先我们可以先求出每个小朋友应该得到的糖果数，就是平均值，然后ave-a[i]就代表要从其他小朋友那得到多少个糖果（如果是负数就是要送出糖果）然后求前缀和，往前面延伸，将值想象成数轴上的点，数轴上任... 查看详情

bzoj1045糖果传递题解递推乱搞就对了

BZOJ1045糖果传递题解【递推乱搞就对了1045:[HAOI2008]糖果传递TimeLimit: 10Sec MemoryLimit: 162MBSubmit: 3505 Solved: 1626[Submit][Status][Discuss]Description　　有n个小朋友坐成一圈，每人有ai个糖果查看详情

bzoj1045题解

1045:[HAOI2008]糖果传递TimeLimit: 10Sec MemoryLimit: 162MBSubmit: 3502 Solved: 1623[Submit][Status][Discuss]Description　　有n个小朋友坐成一圈，每人有ai个糖果。每人只能给左右两人传递糖果。每人每次传递一查看详情

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

...掉一个跑贪心？O（n^2）超时了。。。先计算m为每个最终糖果数量。设An传给A1了k个糖果，那么A1传给A2的糖果数为S1=k+A1-m，T1=A1-m那么A2传给A3的糖果数为S2=k+A1+A2-2*m,T2=A1+A2-2*m那么A3传给A4的糖果数为S3=k+A1+A2+A3-3*m,T3=A1+A2+A3-3*m...那么A... 查看详情

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

[haoi2008]糖果传递

1045:[HAOI2008]糖果传递TimeLimit:10Sec MemoryLimit:162MBSubmit:4184 Solved:2026[Submit][Status][Discuss]Description　　有n个小朋友坐成一圈，每人有ai个糖果。每人只能给左右两人传递糖果。每人每次传递一个糖果代价为1。Input　　第... 查看详情

bzoj1145--糖果传递(贪心)

1045:[HAOI2008]糖果传递TimeLimit: 10Sec MemoryLimit: 162MBSubmit: 4394 Solved: 2155[Submit][Status][Discuss]Description有n个小朋友坐成一圈，每人有ai个糖果。每人只能给左右两人传递糖果。每人每次传递一个糖查看详情

bzoj1045糖果传递

...，于是引用hzw大犇的题解：　　首先，最终每个小朋友的糖果数量可以计算出来，等于糖果总数除以n，用ave表示。　　假设标号为i的小朋友开始有Ai颗糖果，Xi表示第i个小朋友给了第i-1个小朋友Xi颗糖果，如果Xi<0，说明第i-1... 查看详情