P2512 [HAOI2008]糖果传递 题解


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

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

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

评论

  • WuPengrui_666
    orz
  • 453xzz
    dalao, mid应该是b[(n+1)/2]吧QAQ
  • 良辰、
    强啊qaq
  • command_block
    %%%谢谢大佬的题解
  • Rimuru
    %%%
  • Old_Wang
    mid取错了吧
  • Old_Wang
    中位数不是n/2+1或者(n+1)/2吗
  • 随便5057
    p4016样例 5 17 9 14 16 4 输出12 正解11
  • LZDQ
    中位数不一定准确,如果n是奇数没关系,n是偶数要取两个中位数的平均值。就像楼上说的一样
  • LZDQ
    取中间取错了
作者: ysner 更新时间: 2017-10-03 15:34  在Ta的博客查看 举报    55  

觉得楼下不阐明解题思想的题解还是不太好吧

首先,最终每个小朋友的糖果数量可以计算出来,等于糖果总数除以n,用ave表示。

假设标号为i的小朋友开始有Ai颗糖果,Xi表示第i个小朋友给了第i-1个小朋友Xi颗糖果,如果Xi<0,说明第i-1个小朋友给了第i个小朋友Xi颗糖果,X1表示第一个小朋友给第n个小朋友的糖果数量。 所以最后的答案就是ans=|X1| + |X2| + |X3| + ……+ |Xn|。 对于第一个小朋友,他给了第n个小朋友X1颗糖果,还剩A1-X1颗糖果;但因为第2个小朋友给了他X2颗糖果,所以最后还剩A1-X1+X2颗糖果。根据题意,最后的糖果数量等于ave,即得到了一个方程:A1-X1+X2=ave。

同理,对于第2个小朋友,有A2-X2+X3=ave。最终,我们可以得到n个方程,一共有n个变量,但是因为从前n-1个方程可以推导出最后一个方程,所以实际上只有n-1个方程是有用的。

尽管无法直接解出答案,但可以用X1表示出其他的Xi,那么本题就变成了单变量的极值问题。

对于第1个小朋友,A1-X1+X2=ave -> X2=ave-A1+X1 = X1-C1(假设C1=A1-ave,下面类似)

对于第2个小朋友,A2-X2+X3=ave -> X3=ave-A2+X2=2ave-A1-A2+X1=X1-C2

对于第3个小朋友,A3-X3+X4=ave -> X4=ave-A3+X3=3ave-A1-A2-A3+X1=X1-C3

…… 对于第n个小朋友,An-Xn+X1=ave。

我们希望Xi的绝对值之和尽量小,即|X1| + |X1-C1| + |X1-C2| + ……+ |X1-Cn-1|要尽量小。注意到|X1-Ci|的几何意义是数轴上的点X1到Ci的距离,所以问题变成了:给定数轴上的n个点,找出一个到他们的距离之和尽量小的点,而这个点就是这些数中的中位数,证明略。

#include<iostream>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#define ll long long
#define re register
#define il inline
#define fp(i,a,b) for(re int i=a;i<=b;i++)
#define fq(i,a,b) for(re int i=a;i>=b;i--)
using namespace std;
ll a[1000005]={},b[1000005]={},mid,ans,total,n;
il ll gi()
{
    re ll x=0;
    re int t=1;
    re char ch=getchar();
    while((ch<'0'||ch>'9')&&ch!='-') ch=getchar();
    if(ch=='-') t=-1,ch=getchar();
    while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar();
    return x*t;
}
int main()
{
    n=gi();
    fp(i,1,n) a[i]=gi(),total+=a[i];
    total=total/n;
    fp(i,1,n) b[i]=b[i-1]-a[i]+total;
    sort(b+1,b+1+n);
    mid=b[n/2];
    fp(i,1,n) ans+=abs(b[i]-mid);
    printf("%lld\n",ans);
    return 0;
}

评论

  • memset0
    岸芷汀兰,郁郁青青?
  • cliyx
    zzmtxdy
  • 安笙凉城
    zzmtxdy
  • 三旬哇
    zzmtxdy
  • 醉里挑灯看剑
    %%%
  • asuldb
    而或长烟一空,皓月千里
  • Isonan
    浮光跃金,静影沉璧
  • 冰凉的水
    渔歌互答,此乐何及
  • zhou_yk
    登斯楼也,则有心旷神怡,宠辱偕忘,把酒临风,其喜洋洋者矣。
  • JRX2015U43
    怎么想起来岳阳楼记的??
作者: 蒻_努力 更新时间: 2018-04-11 13:11  在Ta的博客查看 举报    42  

作者:岸芷汀兰

一、题目

洛谷原题

二、思路

环形均分纸牌。

没做过的可以做做这道题

一般的均分纸牌问题就相当于在第N个人与第1个人之间把环断开,此时这N个人站成一行,其持有的纸牌数、前缀和分别是:

A[1] S[1]

A[2] S[2]

A[N] S[N]

如果在第K个人之后把环断开站成一行,这N个人持有的纸牌数、前缀和分别是:

A[k+1] S[k+1]-S[k]

A[k+1] S[k+2]-S[k]

A[N] S[N]-S[k]

A[1] S[1]+S[N]-S[k]

A[k] S[k]+S[N]-S[k]

所以,所需最小花费为:$$\sum_{i=1}^{N}|S[i]-S[k]|$$

当K取何值时上式最小?这就是“货仓选址”问题。所以我们将S数组从小到大排序,取中位数作为S[k]就是最优解。

三、代码

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

using namespace std;
inline long long read(void)
{
    long long x=0;int 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 f*x;
}

const int maxn=1000005;

long long n,a[maxn],sum[maxn],ave,ans;

int main()
{
    n=read();
    for(register int i=1;i<=n;i++){
        a[i]=read();ave+=a[i];
    }
    ave/=n;
    for(register int i=1;i<=n;i++)a[i]-=ave;
    for(register int i=1;i<=n;i++)sum[i]=sum[i-1]+a[i];
    sort(sum+1,sum+n+1);
    long long t=sum[(n+1)>>1];
    for(register int i=1;i<=n;i++)ans+=abs(t-sum[i]);
    printf("%lld\n",ans);
    return 0;
}

评论

  • Rye_Catcher
    忘了STL里还有个叫nth_element的神奇操作,之前还用过它在一道优先队列题目里水到90
  • Chasingdreams
  • WHL6666
    太舒服了
  • dreagonm
    orz
  • ysj1173886760
    那个应该是ave-c[i]把 dalao
  • 冰冻赤道
    这个,,诡异的公式。。
作者: LiRewriter 更新时间: 2018-02-13 15:19  在Ta的博客查看 举报    10  

我觉得楼下大佬抄hzwer不太好吧

虽说我大概是抄进阶指南

首先这道题是一个模型,我们称之为环形均分纸牌。显然这个模型是出自luogu1031那道均分纸牌,没有过的可以先过一下。

先来看不是环形的情况。

假设总和为$T$,有$M$张纸牌。设$ave = \dfrac{T}{M}$。对于第i个人来说,如果$C[i] < ave$他拿的应该是$C[i] + ave$张,后一个拿$C[i + 1] - ave + C[i]$,否则,他拿$C[i] - ave$张,而后一个拿$C[i + 1] + C[i] - ave$张。

但是这样并不方便维护,我们考虑整体和隔离的思想。将前i个看做一个整体,显然前i个内部的均分是不会改变其整体结构的,因而对于该体系来说,想要达到平均数结构,就必须与下一个体系交换足够的纸牌,而交换数量就是$|G[i] - i \cdot ive|$,其中$G[i]$是前缀和。然后就可以推出一个结论:$d = \sum ^M _{i = 1} |i \cdot ave - G[i]|$,也就是将每次体系更新的贡献加起来。

如果让每个人的数量都减去$ave$,结果就可以经过简单的数学推导进一步化简:$d = \sum ^M _{i = 1} |S[i]|$,其中$S[i]$是新数组的前缀和。这就是均分纸牌问题的通用公式。

现在考虑一种变形:如果这里的纸牌是环形的呢?

对于环形问题,首先考虑切开。假定我们切开的东西是$A[k + 1], A[k + 2], ..., A[M], A[1], ..., A[k]$,那么其前缀和也会有所变化,即$S[k + 1] - S[k], S[k + 2] - S[k], ..., S[M] - S[k], .S[1] + S[M] - S[k], ..., S[M]$

由于均分之后,$S[M] = 0$恒成立,所以前缀和的变化仅仅是减去$S[k]$。那么,我们要求的就是哪个取值上最短,换言之,求什么时候$\sum^M_{i = 1} |S[i] - S[k]|$取到最小。

因而,这里我们要求的东西是$\sum^M_{i = 1} |S[i] - S[k]|$的最小值。答案是在中位数处取到,原因各位可以想象将$S[i]$投影到一个坐标平面内。然后我们用一条线去扫,点到线的距离之和就是上面的式子的最小值。从中位数的位置变化到靠下的位置或是靠上的位置,都会使某一部分点的距离增大。所以这里转化为求中位数,也就是求第$\dfrac{n + 1}{2}$大元素,由于$N \leq 10^6$所以不建议排序(虽然也能用)。我们可以用STL的kth_elements()函数O(n)求出k大。

#include <iostream>
#include <cstdio>
#include <algorithm>

using namespace std;

typedef long long LL;

LL sum[1000003], S; 

inline void read(LL &x) {
    x = 0; char c = getchar();
    while(!isdigit(c)) c = getchar();
    while(isdigit(c)) x = x * 10 + c - '0', c = getchar();
}
int main() {
    LL n, ans = 0;
    read(n);
    for(int i = 1; i <= n; ++i) read(sum[i]), S += sum[i];
    LL ave = S / n;
    for(int i = 1; i <= n; ++i) sum[i] -= ave;
    for(int i = 1; i <= n; ++i) sum[i] = sum[i - 1] + sum[i];
    int m = (n + 1) / 2;
    nth_element(sum + 1, sum + m, sum + n + 1);
    for(int i = 1; i <= n; ++i) ans += abs(sum[i] - sum[m]);
    cout<<ans<<endl;
    return 0;
}

评论

  • big_news
    费用流+1
  • zhangzitong
    谢谢大佬orz
  • VerakinT
    谢谢
  • Sophon
    巧了
  • Ac_Po_Zn_De_Os
    手动滑稽
  • Ac_Po_Zn_De_Os
    %-%
  • 2018chw
    https://www.luogu.org/blog/2713840045cheng/p2512-haoi2008-tang-guo-zhuan-di-ti-xie,blog食用,效果更佳(滑稽
作者: 2018chw 更新时间: 2019-05-14 17:28  在Ta的博客查看 举报    8  

- 前言:

  1. 看到这题,首先想到费用流,然后....妥妥的MLE

30分Code:

#include<cstdio>
#include<queue>
#include<cstring>
using namespace std;
long long n,sum,cnt=-1,mincost;
long long x[1000100],st[1000100],dis[1000100],vis[1000100],pre[1000100],last[1000100],flow[1000100];
struct edge{
    long long to,next,val,flow;
}e[10001000];
void add(long long u,long long v,long long flow,long long val){
    e[++cnt].to=v;
    e[cnt].flow=flow;
    e[cnt].val=val;
    e[cnt].next=st[u];
    st[u]=cnt;
}
void Add(long long u,long long v,long long flow,long long val){
    add(u,v,flow,val);
    add(v,u,0,-val);
}
bool spfa(long long s,long long t){
    queue<int> q;
    for(long long i=1;i<=n+1;i++)
        dis[i]=2147483647;
    q.push(s);
    vis[s]=true;
    pre[s]=0;
    pre[t]=-1;
    dis[s]=0;
    flow[s]=2147483647;
    while(!q.empty()){
        long long u=q.front();
        q.pop();
        vis[u]=false;
        for(long long i=st[u];i!=-1;i=e[i].next){
            long long v=e[i].to;
            if(e[i].flow>0&&e[i].val+dis[u]<dis[v]){
                dis[v]=dis[u]+e[i].val;
                pre[v]=u;
                last[v]=i;
                flow[v]=min(flow[u],e[i].flow);
                if(!vis[v]){
                    vis[v]=true;
                    q.push(v);
                }
            }
        }
    }
    return pre[t]!=-1;
}
void dinic(long long s,long long t){
    while(spfa(s,t)){
        long long now=t;
        mincost+=flow[t]*dis[t];
        while(now!=s){
            e[last[now]].flow-=flow[t];
            e[last[now]^1].flow+=flow[t];
            now=pre[now];
        }
    }
}
int main(){
    memset(st,-1,sizeof(st));
    scanf("%lld",&n);
    long long s=0,t=n+1;
    for(long long i=1;i<=n;i++){
        scanf("%lld",&x[i]);
        sum+=x[i];
    }
    sum/=n;
    for(long long i=1;i<=n;i++)
        x[i]-=sum;
    for(long long i=1;i<=n;i++){
        if(x[i]>0)
            Add(s,i,x[i],0);
        if(x[i]<0)
            Add(i,t,-x[i],0);
    }
    for(long long i=1;i<=n;i++){
        if(i!=1)
            Add(i,i-1,2147483647,1);
        if(i!=n)
            Add(i,i+1,2147483647,1);
    }
    Add(1,n,2147483647,1);
    Add(n,1,2147483647,1);
    dinic(s,t);
    printf("%lld",mincost);
    return 0;
}

- 正解:


  • 首先,最终每个小朋友的糖果数量可以计算出来,等于糖果总数除以n,假设C1=A1减去最终每个小朋友的糖果数量,设Xi表示第i个小朋友给了第i-1个小朋友Xi颗糖果,
  • 我们希望Xi的绝对值之和尽量小,即|X1| + |X1-C1| + |X1-C2| + ……+ |X1-Cn-1|要尽量小。注意到|X1-Ci|的几何意义是数轴上的点X1到Ci的距离,所以问题变成了:给定数轴上的n个点,找出一个到他们的距离之和尽量小的点,而这个点就是这些数中的中位数,证明应该都懂

    Code:

    #include<cstdio>
    #include<algorithm>
    using namespace std;
    long long a[1000100],x[1000100];//注意数据范围
    long long mid,ans,n,sum;
    int absolute(int x){//手打abs
    if(x<0)
        return -x;
    return x;
    }
    int main(){
    scanf("%lld",&n);
    for(long long i=1;i<=n;i++){
        scanf("%lld",&a[i]);
        sum+=a[i];
    }
    sum/=n;//求最终每个小朋友的糖果数量可以计算出来
    for(long long i=1;i<=n;i++)
        x[i]=x[i-1]-a[i]+sum;
    sort(x+1,x+1+n);
    mid=x[(n+1)/2];//中位数
    for(long long i=1;i<=n;i++)
        ans+=absolute(x[i]-mid);//求最小代价
    printf("%lld",ans);
    return 0;
    }

评论

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

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

设$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)数学写法,而其他的则是简明易懂的正常的、不变态的写法。

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

 
反馈
如果你认为某个题解有问题,欢迎向洛谷反馈,以帮助更多的同学。



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