uva 1388 - Graveyard（数论）

本文主要是介绍uva 1388 - Graveyard（数论），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目链接：1388 - Graveyard

题目大意：在一个周长为10000的圆形水池旁有n个等距离的雕塑，现在要再添加m个雕塑，为了使得n + m个雕塑等距离，需要移动一些雕塑，问如何使得移动的总位移最小，输出最小值。

解题思路：可以将周长展成坐标来看，原来的n个雕塑在x[i] = i / n,而移动过后的位置应该在y[i] = i / (n + m),根据贪心的思想，x[i]肯定要移动到最近的y[j]上，问题就解决了，然后就讨论说会不会有两个雕像移动到同一个位置，大白书里给出了很好的反证法，假设有两个雕塑会移动到同一个位置上，0.5 和1.499999，他们计算过后都会移动到1的位置上去，但是n和m都是小于1000的，即使取得最大值，n + m = 2000， 而圆的周长为10000，所以每两个雕塑之间的距离最小为5。

#include <stdio.h>
#include <stdlib.h>
#include <math.h>int main () {int n, m;while (scanf("%d%d", &n, &m) == 2) {double ans = 0;for (int i = 1; i < n; i++) {double pos = (double) i / n * (n + m);ans += fabs( pos - floor(pos + 0.5) )/ (n + m);}printf("%.4lf\n", ans * 10000);}return 0;
}

这篇关于uva 1388 - Graveyard（数论）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---