UVa 1388 - Graveyard

时间:2023-03-09 14:11:52
UVa   1388 - Graveyard

题意:有一个周长为10000的圆上等距分布着n个雕塑,现在又加入m个雕塑,位置随意,希望n+m个雕塑仍然均匀分布。这就要移动其中一些雕像,求移动的最小距离。

这个题的方法很巧妙,首先将整个圆分成(m+n)份,这样移动后的点都是在整数值上;

所以只要计算在这样的分法下原来的坐标就行了;

#include<cstdio>
#include<cstring>
#include<cmath>
using namespace std;
int main()
{
int n,m;
double pos,ans;
while(scanf("%d %d",&n,&m)!=EOF)
{
ans=0.0;
if(m!=n)
{
for(int i=1;i<n;i++)
{
pos=1.0*i/n*(n+m);
ans+=fabs(pos-floor(pos+0.5))/(n+m);
}
}
printf("%.4lf\n",ans*10000);
}
return 0;
}