UVa1388 - Graveyard (数学,思维)

题目链接

题目描述：在一个周长为10000的圆上等距分布着n个雕塑，现在又有m个新雕塑加入（位置任意放置） 希望所有n+m个雕塑在圆周上均匀分布 这就需要移动其中一些原有的雕塑，要求n个雕塑的移动总距离尽量小。

输入：每行为一个n和m

输出：最小总距离 精确到1e-4

分析：由题目样例我们看到，总有一个雕塑是不需要移动的，事实上我们在推案例的时候也总是先固定一个雕塑，再去考虑其他的距离，我们不需要考虑新加入的m个雕塑如何放置，只需要把这n个雕塑之间的距离变为10000 / (n+m)即可（原来它们之间的距离是(10000)/n).我们先把坐标系缩放为1. 最终结果乘10000即可。

我们把固定的那个雕塑作为坐标轴原点，其余按逆时针序标上到原点的距离

比较难理解的是 ans += fabs(pos - floor(pos+0.5)) / (n+m);

为什么要四舍五入

原因是我们把加入后的n+m个雕塑看作坐标为0，1 ... ,n+m-1

那么固定1个雕塑后 原来的另外n-1的雕塑一定不是一个整数

我们如何确定2个雕塑不会移动到同一个位置呢？

考虑极端情况 a = 0.5 b = 1.49999999  那么a,b四舍五入的结果均是1 但这是不可能的 因为它们的距离小于1

而加入m个雕塑以后 原先的雕塑之间距离一定会减小 因为要插入雕塑。

因而算法是正确的。

代码：

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>

using namespace std;

int n,m;

int main()
{
	while(scanf("%d %d",&n,&m) == 2)
	{
		double ans = 0.0;
		for(int i = 1;i<n;i++)
		{
			double pos = (double) i/n*(n+m);	//计算原先的n个雕塑的原始坐标，此时圆的量纲已经不是单位1 而是n+m
			ans += fabs(pos - floor(pos +0.5)) / (n+m);	//四舍五入后为现在的坐标 两者之差为移动距离,注意要把量纲转为1
		}
		printf("%.4lf\n",ans * 10000);
	}	
}