bzoj1045[haoi2008]糖果传递

Visitor Visitor     2022-10-23     810

关键词:

【链接】 我是链接,点我呀:)
【题意】


在这里输入题意

【题解】


思路来自hzwer..
设xi表示第i个人往左传递了xi个糖果。
(如果小于0表示旁边的人给他了糖果。
则ans=∑|xi|
最后所有人的糖果数都变成sum/n->avg

a1-x1+x2 = avg
a2-x2+x3= avg
...

然后可以用avg和x1来表示所有的x2...xn
比如
x2 = x1-(avg-a1)
x3 = x1-(2avg-a1-a2)
....
会发现x1右边的式子都是常量。
且都是x1-ci的形式

那么就相当于有n个点。
然后现在让你选择一个点x1.
使得∑|x1-ci|最小。
显然选择所有这些点里面的中位数就好。
(即ci的中位数
(ci可以观察形式,用递推的方法得到

【代码】

#include <bits/stdc++.h>
#define LL long long
#define rep1(i,a,b) for (int i = a;i <= b;i++)
#define rep2(i,a,b) for (int i = a;i >= b;i--)
#define all(x) x.begin(),x.end()
#define pb push_back
#define ls l,mid,rt<<1
#define rs mid+1,r,rt<<1
using namespace std;

const double pi = acos(-1);
const int dx[4] = 0,0,1,-1;
const int dy[4] = 1,-1,0,0;
const int N = 1e6;

int n;
int a[N+10],c[N+10];

int main()
    #ifdef LOCAL_DEFINE
        freopen("rush_in.txt", "r", stdin);
    #endif
    scanf("%d",&n);
    rep1(i,1,n)
        scanf("%d",&a[i]);
    LL sum = 0;
    rep1(i,1,n) sum+=a[i];
    sum/=n;
    c[1] = sum-a[1];
    rep1(i,2,n-1) c[i] = c[i-1] + sum-a[i];
    c[n] = 0;
    sort(c+1,c+1+n);
    LL x1 = c[n/2+1];
    sum = 0;
    rep1(i,1,n)
        sum+=abs(x1-c[i]);
    printf("%lld\n",sum);
    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]糖果传递

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

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]糖果传递(代码片段)

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

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

[haoi2008]糖果传递

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