题意:在一个周长为10000的圆上等距分布着n个雕塑,现在又有m个新雕塑加入,位置可以随意放,希望所有的n+m个雕塑在圆周上均匀分布,这就需要移动其中一些原有的雕塑,要求n个雕塑移动的总距离最小,输出这个最小值
分析:把点转化为相对坐标,先缩小n倍再放大n+m倍,得到新坐标pos,并取离pos最近的整点,两者之差的绝对值再缩小n+m倍就是需要移动的距离,所有的点的移动距离累加即可。floor(pos+0.5)表示距离pos最近的整数点
代码:
#include <iostream> #include <stdio.h> #include <math.h> using namespace std; int main(){ int n, m; while(scanf("%d%d", &n, &m)!=EOF){ int i; double ans = 0; for(i=1; i double pos = (i*1.0/n)*(n+m); double ret = floor(pos+0.5); ans += fabs(ret - pos)/(n+m); } printf("%.4lf\n", ans*10000); } return 0; }