Graveyard UVA - 1388

思维 圆分割 坐标缩小 T2 Graveyard - UVA 1388 - Virtual Judge --- 墓地 - UVA 1388 - 虚拟裁判 (csgrandeur.cn)

在一个周长为 $10000$ 的圆上等距分布着 $n$ 个雕塑。现在又有 $m$ 个新雕塑加入（位置可以随意放），希望所有 $n＋m$ 个雕塑在圆周上均匀分布。

这就需要移动其中一些原有的雕塑。要求$n$个雕塑移动的总距离尽量小。

输入

输入包含若干组数据。每组数据仅一行，

包含两个整数 $n$ 和 $m（2\le n\le 1000，1\le m\le 1000）$，即原始的雕塑数量和新加的雕塑数量。

输入结束标志为文件结束符（EOF）。

输出

输出仅一行，为最小总距离，精确到$10^{-4}$。

样例

输入

2 1
2 3
3 1
10 10

输出

1666.6667
1000.0000
1666.6667
0.0000

思路

参考博客：UVA1388（刘汝佳白书例题）无问的博客-CSDN博客 思路及图片来自于算法入门经典-训练指南

周长为 $10000$ 的圆原先被分成 $n$ 分, 现在要多分出 $m$ 份, 总共 $n+m$ 分, 给出一种最小的方案, 使得原本 $n$ 份移动的部分最小。

考虑先让原本的一个位置固定不动, 作为新位置的第一个位置。接下来求出剩余的原位置附近距离最小的新位置, 就是答案。

原位置在原图中为 $\frac{i}{n}$, 而加入 $m$ 个点后, 在原位置在新图中的位置就被变换为 $\frac{i}{n}\times (n+m)$ , 而新图中的新位置就是 $\frac{i}{n+m}$。 但直接累加 $\sum _{i=1}^{n-1}\{\frac{i}{n}\times (n+m)-\frac{i}{n+m}\}$ 并不成立, 不一定是最近的新位置, 正确方法是将 原位置$pos$ 进行四舍五入到一个最近的整点, 然后再减去原来的差值, 才是正确的距离。即 $\sum _{i=1}^{n-1}\{\frac{round\{po{s}_i\}-po{s}_i}{n+m}\}$ 。

代码

#define setPrec(n) cout << fixed << setprecision(n)
#include <bits/stdc++.h>
using namespace std;
// #define debug
int n, m;
 
void solve()
{
    setPrec(4);
    double res = 0;
    for (int i = 1; i < n; i++)
    {
        double pos = (double)i / n * (n + m);
        res += fabs(round(pos) - pos) / (m + n);
    }
    cout << res * 10000 << endl;
}
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    while (cin >> n >> m)
    {
        solve();
    }
    return 0;
}