P2512 [HAOI2008]糖果传递 题解


以下题解仅供学习参考使用。

抄袭、复制题解,以达到刷AC率/AC数量或其他目的的行为,在洛谷是严格禁止的。

洛谷非常重视学术诚信。此类行为将会导致您成为作弊者。具体细则请查看洛谷社区规则

评论

  • summerrain
    tql%%%%
  • wang98
    orz tql
作者: wyhwyh 更新时间: 2019-05-19 19:48  在Ta的博客查看 举报    7  

首先我们要用到一些均分纸牌的思想(已经理解这种思想的大佬请跳过):

设$A_i$表示第$i$个小朋友原有的糖果数量,

设$ave$表示所有小朋友糖果数量的平均数,

$X_i$表示第$i$个小朋友向左传的糖果数量。即:

①如果$X_i>0:\quad$ 第$i$个小朋友向左传$X_i$个糖果;

②否则如果$X_i<0:\quad$ 第$i$个小朋友向左传$|X_i|$个糖果。

所以该题的代码为:

Code:


#include<cstdio>
int a[101];
int n,x,s;
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;++i)
    {
        scanf("%d",&a[i]);
        x+=a[i];
    }
    x/=n;
    for(int i=1;i<n;++i)
    {
        a[i]-=x;
        if(a[i]!=0)
        {
            ++s;
            a[i+1]+=a[i];
        }
    }
    printf("%d",s);
    return 0;
}

好现在让我们回到原题糖果传递上来。

看看刚刚设的什么:

设$A_i$表示第$i$个小朋友原有的糖果数量,

$ave$表示所有小朋友糖果数量的平均数,

$X_i$表示第$i$个小朋友向左传的糖果数量。

则由题可得方程: $$ A_1+X_2-X_1=ave $$ $$ A_2+X_3-X_2=ave $$ $$ ··· $$ $$ A_n+X_1-X_n=ave $$ 即:

$$A_i+X_{i+1}+X_i=ave(1\le i<n)$$

$$A_n+X_1+X_n=ave(i=n)$$

变形得: $$ X_2=ave+X_1-A_1 $$ $$ X_3=ave+X_2-A_2=ave+(ave+X_1-A_1)-A_2=2ave-A_1-A_2+X_1 $$ $$ ··· $$ $$ X_1=ave+X_n-A_n=n·ave-A_1-A_2-…-A_n+X_1 $$

这时我们设: $$ C_1=A_1-ave $$ $$ C_2=A_1+A_2-ave $$ $$ ··· $$ $$ C_n=A_1+A_2+…+A_n-n·ave $$

即设:

$$C_i=\sum_{j=1}^iA_j-i·ave(1\le i\le n)$$

则有: $$ X_2=X_1-C_1 $$ $$ X_3=X_1-C_2 $$ $$ ··· $$ $$ X_n=X_1-C_n $$

即:

$$X_i=X_1-C_i$$

这时我们返回来看所求,要求传递价值最小,

这就是说,要求最小化 $$ |X_1|+|X_2|+···+|X_n| $$ 而该式等于 $$ |X_1-C_1|+|X_1-C_2|+···+|X_1-C_n| $$

即求:

$$MIN \{ \sum_{i=1}^nX_i \}=MIN \{ \sum_{i=1}^nX_1-C_i \}$$

这样就好办了,$C_i$是已知(额,至少是可以预处理出来)的,要想最小化上式,我们把$C_i$看成数轴上的一个个点,现在问题就转化成了找出一个点$X_1$,使得她到各个$C_i$上的点的距离和最小。

显然,这个点就是这$n$个点的中位数。。。(一会再给出数学证明)

那么求出了$X_1$之后,根据 $$ X_2=X_1-C_1 $$ $$ X_3=X_1-C_2 $$ $$ ··· $$ $$ X_n=X_1-C_n $$

这一坨柿子,我们可以求出$X_2,X_3…X_n$,然后就可以偷税的得到所求的:

最小化 $$ |X_1|+|X_2|+···+|X_n| $$

啦233~~~

代码好丑,大家别嫌弃qwq:

Code:


#include<bits/stdc++.h>
#define max(a,b) a>b?a:b
#define min(a,b) a<b?a:b
#define inline il

typedef long long ll;
typedef long double ld;

const int inf = 0x7fffffff;
const int N = 1e6+1;

ll n;
ll a[N],c[N];
ll ave,ans,mid;

using namespace std;

int main()
{
    scanf("%lld",&n);
    for(int i=1;i<=n;++i)
        scanf("%lld",&a[i]),ave+=a[i];
    ave/=n;
    for(int i=1;i<=n;++i)
        c[i]=c[i-1]+ave-a[i-1];
    sort(c+1,c+n+1);
    mid=c[(n+1)/2];
    for(int i=1;i<=n;++i)
        ans+=abs(mid-c[i]);
    printf("%lld",ans);
    return 0;
}

附:数学证明

在数轴上有$n$个点,找出一个点$x$,使得她到各个点的距离和最小。

求证:该点表示的数就是这$n$个数的中位数。

如果我们把数轴上的点两两配对,最大的配最小的,次大的配次小的……

则到每组点最近的距离的点在这两个点中间,那么

如果有奇数个点,那么显然中间那个点便为所求。

该点表示的数是这$n$个数的中位数得证。

注:有一些柿子在文中以不同的形式重复出现,主要是为了同时满足大佬和蒟蒻的需要。一些前面写了‘即…’并用

这个东西

框起来的一般是适合大佬的较严(bian)格(tai)数学写法,而其他的则是简明易懂的正常的、不变态的写法。

希望大家喜欢,点个赞哦:)

评论

  • Mcggvc
    (C2=A1+A2-X2-2ave) 这个-X2怎么来的???
  • whwh
    (C2=A1+A2-X2-2ave) 写错了
  • whwh
    没有X2,下面的也是
作者: _zjz 更新时间: 2018-08-15 20:11  在Ta的博客查看 举报    5  

题目描述:

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


解:

最终的局面是每个小朋友的糖果数量相同,即为平均数(ave);

设标号为i的小朋友初始有ai个糖果.

xi表示第i个小朋友给第i-1个小朋友xi个糖果 (x1给xn糖果)

容易发现ans=|x1|+|x2|+|x3|......+|xn|;

对于第1个小朋友 易列出a1-x1+x2=ave

依次类推:

易得:

x1=x1-0;

X2=ave-A1+X1=X1-C1 (C1=A1-ave)

X3=2ave-A1-A2+X1+X2=X1-C2 (C2=A1+A2-X2-2ave)

X4=3ave-A1-A2-A3+X1+X2+X3=X1-C3

(C3=A1+A2+A3-X2-X3-3ave)

其中ci可在O(n)时间内预处理出来. ........

ans=|x1|+|x1-c1|+.....|x1-cn-1|.

几何意义即为x1距0,c1,.....cn-1距离和最小

x1取中位数即可。

为什么x1取中位数最小?

当在中位数偏右的位置,向左移的时候左边的点距该点 距离减少d,贡献为左边的点个数*d,

右边的增加右边的点个数*d.左边同理

发现只有在中间的时候达到最小........

详见代码:

// luogu-judger-enable-o2
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cctype>

typedef long long ll;
using namespace std;

const int N=1000001;
ll a[N],s[N];

inline ll read()
{
    ll X=0,w=0;char ch=0;
    while(!isdigit(ch))
    {
        w|=ch=='-';ch=getchar();
    }
    while(isdigit(ch))
    {
        X=X*10+ch-'0';ch=getchar();
    }
    return w?-X:X;
}

int main()
{
//  freopen("candy.in","r",stdin);
//  freopen("candy.out","w",stdout);
    ll n,sum=0;
    n=read();
    for(int i=1;i<=n;i++)
    {
       a[i]=read();
       sum+=a[i];
    }
    int x=sum/n;
    for(int i=2;i<=n;i++)
    s[i]=s[i-1]+x-a[i];//求ci
    sort(s+1,s+n+1);
    ll k=s[(n+1)/2];//取中位数
    ll ans=0;
    for(int i=1;i<=n;i++)
    {
         ans+=abs(k-s[i]);//计算答案
    }
    cout<<ans;
    fclose(stdin);
    fclose(stdout);
    return 0;
}

评论

  • GoldenPotato137
    dalao,您的题解在“还有”这局话只有的第一个柿子写错了一个地方,第一个柿子应该是 $a_2-X_2+X_3=ave$,多了一个$-a$
  • ViXpop
    柿子好评
作者: Palace 更新时间: 2018-10-08 20:51  在Ta的博客查看 举报    3  

走你

思路:

这是个环形的均分纸牌

在这里记录一下zhw的数学做法。

我们设$X_i$表示第$i$个人需要给第$i-1$个人的糖果,设最后每人手中都有$ave$块糖,则$ans=\sum_{i=1}^n|X_i|$,那么:

$a_i-X_i+X_{i+1}=ave$

那么,

$a_1-X_1+X_2=ave$ $=>$ $X_2=ave-a_1+X_1$

令$C_1=a_1-ave$

那么,

$X_2=X_1-C_1$

还有,

$a_2-X_2+X_3=ave-a$ $=>$ $X_3=ave+X_2-a_2$ $=>X_3=2×ave-a_1-a_2+X_1$ $=>$ $X_1-C_2$

...

我们发现$C_i=sum_i-ave×i$,我们就得到了求$C_i$的方法,而对于$X_i=X_1-C_{i-1}$。

所以$ans=\sum_{i=1}^n|X_i|=|X_1-0|+|X_2-C_1|+...+|X_n-C_{n-1}|$

根据数学知识,这个式子表示$X_1$到数轴上$C_0$ 到 $C_{n-1}$的点的距离之和,所以$X_1$取中位数时,$ans$最小。

代码:

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>

#define N 1000010
#define LL long long

using namespace std;

LL n, ave, ans;
LL a[N], c[N], x[N], cc[N], s[N];

int main() {

    scanf( "%lld", &n );
    for( LL i = 1; i <= n; ++i ) {
        scanf( "%lld", &a[i] );
        s[i] = s[i - 1] + a[i];
    }

    ave = s[n] / n;
    for( LL i = 1; i <= n - 1; ++i ) {
        c[i] = s[i] - ( ave * i );
        cc[i] = c[i];
    } 
    sort( cc + 1, cc + 1 + n - 1 );

    x[1] = cc[( n + 1 ) >> 1];
    for( LL i = 2; i <= n; ++i )
        x[i] = abs( x[1] - c[i - 1] );
    x[1] = abs( x[1] );
    for( LL i = 1; i <= n; ++i )
        ans += x[i];
    printf( "%lld\n", ans );
    return 0;
} 

评论

  • 还没有评论
作者: C20203030 更新时间: 2019-10-21 21:38  在Ta的博客查看 举报    1  

一、题目

点此看题

二、解法

设$x_i$为$i$号给$i-1$号$x_i$颗糖果(如果为负则方向相反),让后我们可以列出下面的式子:

$a_1-x_1+x_2=ave$

$\dots \dots$

$a_i-x_i+x_{i+1}=ave$

发现有$n-1$个方程,$n$个未知数,可以解出关系式(定义$c[i]=\sum_{j=1}^{i} a[j]-ave$):

$x_i=x_1-c[i-1]$

我们的答案就是$|x_1|+|x_1-c[1]|+...+|x_1-c[n-1]|$

可以发现这就是个小学的邮局问题,取$c$的中位数即可。(说中位数可能有点不严谨,详细操作看代码吧)

#include <cstdio>
#include <algorithm>
using namespace std;
#define int long long
const int MAXN = 1000005;
int read()
{
    int x=0,flag=1;char c;
    while((c=getchar())<'0' || c>'9') if(c=='-') flag=-1;
    while(c>='0' && c<='9') x=(x<<3)+(x<<1)+(c^48),c=getchar();
    return x*flag;
}
int n,ave,ans,a[MAXN],s[MAXN];
int _abs(int x)
{
    return x>0?x:-x;
}
signed main()
{
    n=read();
    for(int i=1;i<=n;i++)
    {
        a[i]=read();
        ave+=a[i];
    }
    ave/=n;
    for(int i=1;i<n;i++)
        s[i]=s[i-1]+a[i]-ave;
    sort(s+1,s+n);
    int x1=s[(n+1)/2],val=_abs(x1);
    for(int i=1;i<n;i++)
        ans+=_abs(x1-s[i]);
    n--;
    if(n%2==0) val=min(_abs(s[n/2]),_abs(s[n/2+1]));
    printf("%lld\n",ans+val);
}

评论

  • Sakura_梦瑶
    最终状态ans那个式子的ci 应该是sumc[i]这样子的一个东西吧
作者: BeyondLimits 更新时间: 2019-03-01 16:09  在Ta的博客查看 举报    1  

思路:看一眼题目是环形均分纸牌。

我们设$X_i$表示第$i$个人给第$i-1$个人的糖果数。

则最终答案为:

$$ans=\sum_{i=1}^n abs(X[i])$$

特殊的是:$X_1$表示第$1$个人给第$n$个人的糖果数。

设: $$s=(\sum_{i=1}^n a[i] )/n$$

目标状态下,则:

$i=1$时,$s=a_1-X_1+X_2$

$i=2$时,$s=a_2-X_2+X_3$

$i=3$时,$s=a_3-X_3+X_4$

$......$

$i=n$时,$s=a_n-X_n+X_{n-1}$

化成另一种形式:

$X_2=s-a_1+X_1$

$X_3=s-a_2+X_2$

$X_4=s-a_3+X_3$

$......$

$X_n=s-a_{n-1}+X_{n-1}$

我们使$C_i=a_i-s$,则上面形式可以得到简化,即为:

$X_2=X_1-C_1$

$X_3=X_2-C_2$

$X_4=X_3-C_3$

$......$

$X_n=X_{n-1}-C_{n-1}$

把上面式子中的$C$数组展开,显然发现有关$C$数组运算可以使用前缀和处理。

由此,答案转化成了:

$$ans=\sum_{i=1}^n abs(X_1-C_i)$$

显然:

$$ X_1∈C[i],i∈[1,n] $$

我们希望答案最小,转化为数学意义,则最终问题即为,在一个数轴上选出一个点,使得这个点到其他点的距离和最小,则这个点为所有数字中的中位数,证明在此不多赘述。

代码:

#include <cstdio>
#include <cctype>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <cmath>
typedef long long ll;
static const int MAXN=1000050;
using namespace std;
ll n,sum,s,ans,c[MAXN],a[MAXN];
inline ll read(){
    ll x=0;bool sign=false;
    char alpha=0;
    while(!isdigit(alpha)) sign|=alpha=='-',alpha=getchar();
    while(isdigit(alpha)) x=(x<<1)+(x<<3)+(alpha^48),alpha=getchar();
    return sign?-x:x;
}
int main(){
    n=read();
    for(int i=1;i<=n;i++){
        a[i]=read();
        sum+=a[i];
    }
    s=sum/n;
    for(int i=1;i<=n;i++){
        c[i]=c[i-1]+a[i]-s;
    }
    sort(c+1,c+n+1);
    for(int i=1;i<=n;i++) ans+=abs(c[i]-c[(n>>1)+1]);
    printf("%lld\n",ans);
    return 0;
}
 
反馈
如果你认为某个题解有问题,欢迎向洛谷反馈,以帮助更多的同学。



请具体说明理由,以增加反馈的可信度。