La3708Graveyard<数学题>

链接:https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=1709

题意:

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

思路:

以其中一点为原点,把圆拉直, 初始坐标为1/n, 2/n, ~~(n-1)/n; 目标坐标为1/(n+m), 2/(n+m), ~~ (n+m-1)/(n+m),

要使移动距离最小, 则把初始位置的雕像移到离他最近的位置即可; 设原来第 i 个雕像移动到 x/(m+n)位置最佳,

i/n == x/(n+m) ==>   x= i / n * (n+m), 若 x 为整数,即为所求, 若不是, 必是 floor(x) 和 ceil( x )中的一个;

#include <cstdio>
#include <cmath>
#include <algorithm>
#include <stdlib.h>
using namespace std;

int main() {
  int n, m;
  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);         //计算每个需要移动到的雕塑的坐标
          ans+=min( fabs(i*1.0/n-floor( pos )*1.0/(n+m)), fabs( i*1.0/n-ceil( pos )*1.0/(n+m)) );
    }
    printf("%.4lf\n", ans*10000);                 //等比例扩大坐标
  }
  return 0;
}