P2512 [HAOI2008]糖果传递 题解

CSDN同步

原题链接

简要题意:

一开始每个人有若干糖果,每个人每次将 $1$ 个糖果传递给 相邻(认为 $1$ 号与 (n) 号也相邻)的一个人 需要 $1$ 的代价。求让所有人的糖果一样的最小代价。

显然,如果 $1$ 号与 (n) 号不相邻,那就退化了成了 P1031 均分纸牌,但 理想是美好的,现实是残酷的,所以我们要着手环的问题。

算法一

破环为链。

考虑在哪里把环切断,然后暴力跑均分纸牌的贪心。

时间复杂度:(O(n^2)).

实际得分:$0pt$ ~ $100pts$.(出题人没写部分分)

算法二

首先我们算出 (frac{sum_{i=1}^n a_i}{n}) 即平均数。

然后,用 (x_i) 表示 (i) 号给了 (i-1) 号若干糖果,而 (x_1) 就是 $1$ 号给了 (n) 号若干糖果。如果 (x_i < 0) 则说明是 (i-1) 号((i=1) 时为 (n) 号) 给了 (i) 号若干糖果。并用 (c_i) 表示 (i) 号节点 比平均糖果多的值,少则为负数,然后 (c_i) 对自己做前缀和。

这时,我们想要最小化 (x_i) 的绝对值之和,也即:

(|X| + sum_{i=1}^{n-1} |X - c_i|)

为什么呢?你可以这样理解,每一组给糖果的关系就是前缀和的差,然后你搞出一个点叫做 (X) 实现这个过程。

然后你看一眼这个式子,你发现 (X_1 - c_i)数轴上表示 (X_1) 的点到表示 (c_i) 的点的距离(来自小学数学老师),然后问题就退化为:

找一个 (X) 使得它与 每一个 (c_i) 的距离之和最小。

这小学贪心题啊,取中位数就行了。

时间复杂度:(O(n log n)).(主要是 取中位数要排序,如果用数据结构可能会优化到线性)

实际得分:$100pts$.

#pragma GCC optimize(2)
#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
const int N=1e6+1;

inline ll read(){char ch=getchar();int f=1;while(ch<'0' || ch>'9') {if(ch=='-') f=-f; ch=getchar();}
	ll x=0;while(ch>='0' && ch<='9') x=(x<<3)+(x<<1)+ch-'0',ch=getchar();return x*f;}

ll a[N],x[N],ans=0;
ll n,sum=0; //sum 是平均数

int main(){
	n=read();
	for(int i=1;i<=n;i++) sum+=(a[i]=read());
	sum/=n; for(int i=1;i<=n;i++) x[i]=x[i-1]+sum-a[i]; //前缀和差值
	sort(x+1,x+1+n); int mid=x[(n+1)>>1]; //排序中位数
	for(int i=1;i<=n;i++) ans+=abs(x[i]-mid); //统计差值答案
	printf("%lld
",ans);
	return 0;
}

【推广】 免费学中医,健康全家人
原文地址:https://www.cnblogs.com/bifanwen/p/12661185.html