bzoj1145--糖果传递(贪心)

关键词：

Description

Input

Output

Sample Input

Sample Output

题目链接：

　　　　http://www.lydsy.com/JudgeOnline/problem.php?id=1145 

Solution

　　　　显然最后每个小朋友分到的糖数 s 是可以直接算的。。。

　　　　假设刚开始每个第 i 个小朋友有 k [ i ] 个糖。。第 i 个小朋友给第 i - 1 个小朋友 t [ i ] 个糖，第 n 个小朋友给第一个小朋友 t [ n ] 个糖。。

　　　　于是可以列出方程：  k [ i ] - t [ i ] + t [ i + 1 ] = s

　　　　记 C [ i ] = ∑ ( k [ j ] - s ) (1 <= j <= i )

　　　　于是:

　　　　　　 t [ 2 ] = s - k [ 1 ] + t [ 1 ] = t [ 1 ] - C [ 1 ]

 　　　　　　t [ 3 ] = s - k [ 2 ] + t [ 2 ] = 2*s - k [ 2 ] - k [ 1 ] + t [ 1 ] = t [ 1 ] - C [ 2 ]

　　　　　　 t [ 4 ] = t [ 1 ] - C [ 3 ]

　　　　　　。。。

　　　　我们要求的是 ∑ | t [ i ]  - C [ i - 1 ] | ，实质上就是给出数轴上若干个点 C0 ，C1 ，C2 。。。。 然后求一个点 x 使得总距离最小。。。

　　　　显然用最中间的那个点是最优的。。。

代码

#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<iostream>
#define N 1000050
#define LL long long
using namespace std;
inline int Read(){
    int x=0,f=1;char ch=getchar();
    while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();}
    while(ch>=‘0‘&&ch<=‘9‘){x=x*10+ch-‘0‘;ch=getchar();}
    return x*f;
}
int n;
int k[N],t[N];
LL mid,ans,s;
int main(){
    n=Read();
    for(int i=1;i<=n;i++){
        k[i]=Read();s+=k[i];
    }
    s=s/n;
    for(int i=1;i<=n;i++)
        t[i]=t[i-1]-k[i]+s;
    sort(t+1,t+n+1);
    mid=t[n/2];
    for(int i=1;i<=n;i++)
		ans+=abs(t[i]-mid);
    printf("%lld
",ans);
    return 0;
}

This passage is made by Iscream-2001.

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

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

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

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

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

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

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

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

糖果传递（基于贪心的数学问题）(代码片段)

0807糖果传递 0x08「基本算法」练习描述有n个小朋友坐成一圈，每人有a[i]个糖果。每人只能给左右两人传递糖果。每人每次传递一个糖果代价为1。求使所有人获得均等糖果的最小代价。输入格式第一行一个正整数n<=1000000，... 查看详情

bzoj1045:[haoi2008]糖果传递

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

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

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

bzoj1045糖果传递

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

bzoj1045[haoi2008]糖果传递

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

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

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

糖果传递贪心+找规律(代码片段)

...题其实是贪心。假设有n个小朋友，每个小朋友有ai个糖果，小朋友给出去的为xi，平均数为avg每个小朋友手上剩余的：1:a1+x2-x1=avg;//自己手上有的ai，给出去的xi，收到的x&#x 查看详情

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

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

bzoj1045糖果传递(代码片段)

真·水题。环形均分纸牌模板题。只需求出前缀和，然后取中位数求二重前缀和即可。1#include<cstdio>2#include<algorithm>3usingnamespacestd;4typedeflonglongLL;5constintN=1000010;6LLa[N],sum[N];7intmain()8intn;9scanf("%d",&n);10fo 查看详情

bzoj1045糖果传递

...们可以设i个人开始有ai个糖然后设第i个人给前一个人的糖果数为gi则a[i]-g[i]+g[i+1]=avg；avg为最终每个人的糖果数即平均值得到最终答案为所有abs(g[i])设p数组表示a1+...+a[i]-i*avg 则a[1]-g[1]+g[2]=avg→g[2]=avg-a[1]-g 查看详情

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

...掉一个跑贪心？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]糖果传递

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

p2512糖果传递(贪心)(施工中)(代码片段)

题目链接解题思路??这一题相当于环形的均分纸牌，需要用到均分纸牌的思路。??在均分纸牌这题中，我们可以从最左边的一堆或者最右边的一堆开始，递推出所有牌堆需要传递的次数，设每传一张牌的代价为1，那么把(x_i)累加... 查看详情