β

搬运树苗 二分+贪心

Dianlujitao 84 阅读

搬运树苗( move

输入文件:move.in

输出文件:move.out

【问题描述】

Neyc的绿化工程正在进行,树苗已经被工人送到园区内。设计师希望将树苗种植成一个环形的绿化带,这个绿化带有n个树苗群,而每个树苗群有相同数量的树苗。但是在卸放树苗时,工人虽然按环形排列将树苗放置了n堆,但是每一个树苗群的树苗数量却没有满足要求。

于是,需要从任意一个树苗群中取任意数量的树苗搬运到相邻的树苗群,使得每个树苗群树苗的数量相等。

为了节约时间,现在需要找到一种搬运方式:搬运最少的树苗使得每一个树苗群的树苗数目相同。

当然,每个树苗群的树苗数量是已知的,分别是m 1, m 2 ……….m n ,且S=m 1 +m 2 ….m n 必为n的倍数。

例如:n=5,每个树苗群的树苗数量分别为17 9 14 16 4,我们进行如下搬运;

(1)    树苗群1向树苗群2搬运1棵树苗;

(2)    树苗群1向树苗群5搬运4棵树苗;

(3)    树苗群3向树苗群2搬运2棵树苗;

(4)    树苗群4向树苗群5搬运4棵树苗;

搬运树苗的总数是1+4+2+4=11,并且可以证明这样的搬运方式是最佳的搬运方法。

【输入格式】

第一行正整数n(n<=10000),表示有n个树苗群;

第二行n个整数(integer范围),表示n个树苗群的树苗数量。

【输出格式】

一个正整数,表示最少搬运树苗的数量。

【样例输入】

5

17 9 14 16 4

【样例输出】

11

分析:

读入时将环状拆成链状,即m数组开到maxn的两倍,同时读入m[i]和m[n+i]。然后枚举1~n的情况,模拟移动,求出当前的值,取最小值存到数组中,最后输出这个数组的最小值。注意有一组数据爆int,要用long long。

代码:


#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
int sum=0,n,m[20010]={0};
long long f[20010]={0};
int t=0;
void init()
{
	freopen("move.in","r",stdin);
	freopen("move.out","w",stdout);
}
void input()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&m[i]);
		m[n+i]=m[i];
		sum+=m[i];
	}
	sum/=n;
}
void solve()
{
	for(int i=1;i<=n;i++)
	{
		t=0;
		for(int j=1;j<=n;j++)
		{
			f[i]+=abs(t);
			t+=m[i+j-1]-sum;
		}
	}
	printf("%I64dn",*min_element(f+1,f+n+1));
}
int main()
{
	init();
	input();
	solve();
	return 0;
}
作者:Dianlujitao
只有面对现实,才能超越现实
原文地址:搬运树苗 二分+贪心, 感谢原作者分享。