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的博客查看 举报    39  

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

首先,最终每个小朋友的糖果数量可以计算出来,等于糖果总数除以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的博客查看 举报    32  

作者:岸芷汀兰

一、题目

洛谷原题

二、思路

环形均分纸牌。

没做过的可以做做这道题

一般的均分纸牌问题就相当于在第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
作者: 2018chw 更新时间: 2019-05-14 17:28  在Ta的博客查看 举报    5  

- 前言:

  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;
    }

评论

  • 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;
}
 
反馈
如果你认为某个题解有问题,欢迎向洛谷反馈,以帮助更多的同学。



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