P2512 [HAOI2008] 糖果传递

方法一：

费用流，过不了

方法二：

不难发现，传递路线不会交叉，所以如果题目不是环，是序列的情况下，可以直接

O(n)

贪心解决

考虑破环，枚举

1

号点和

n

号点传递的量，即可变成序列的情况

显然会超时，不难发现是单峰函数，三分即可，时间复杂度为

O(n\log n)

代码：

CPP

#include<bits/stdc++.h>
#define int long long 
using namespace std;
const int N=1e6+50,inf=2e9;
int n,a[N],b[N],ans=1e18,to;
int work(int x){
	int tot=abs(x);
	for(int i=1;i<=n;i++) b[i]=a[i];
	b[n]+=x; b[1]-=x;
	for(int i=1;i<n;i++){
		if(b[i]<to) tot+=to-b[i],b[i+1]-=to-b[i];
		else tot+=b[i]-to,b[i+1]+=b[i]-to;
	}
	return tot;
}
main(){
	scanf("%lld",&n);
	for(int i=1;i<=n;i++) scanf("%lld",&a[i]),to+=a[i];
	to/=n;
	int L=-inf,R=inf;
	while(L+3<=R){
		int x=L+(R-L)/3,y=L+(R-L)*2/3;
		if(work(x)<work(y)) R=y-1; 
		else L=x;
	}
	for(int i=L;i<=R;i++) ans=min(ans,work(i));
	printf("%lld\n",ans);
}

方法三：

设

x_i

为

i-1

号点传递给

i

号点的个数，

x_1

为

n

给

1

的

那么有

a_i+x_i-x_{i+1}=to

，即

x_{i+1}=(a_i-to)+x_i

设

c_i=a_i-to

，则

x_i=x_1+\sum_{j=1}^{i-1}c_j

答案为

\sum_{i=1}^n |x_i|

，排序后让

x_1

取中位数即可

代码：

CPP

#include<bits/stdc++.h>
#define int long long 
using namespace std;
const int N=1e6+50;
int n,a[N],to,c[N],ans;
main(){
	scanf("%lld",&n);
	for(int i=1;i<=n;i++) scanf("%lld",&a[i]),to+=a[i];
	to/=n;
	for(int i=2;i<=n;i++) c[i]=c[i-1]+a[i-1]-to;
	sort(c+1,c+n+1);
	int x=-c[(n+1)/2];
	for(int i=1;i<=n;i++) ans+=abs(x+c[i]);
	printf("%lld\n",ans);
}

P2512 [HAOI2008] 糖果传递

文章操作

P2512 [HAOI2008] 糖果传递

方法一：

方法二：

代码：

方法三：

代码：

相关推荐

评论

P2512 [HAOI2008] 糖果传递