LA 3708 墓地雕塑（模拟）

时间：2021-05-13 14:56:50

题目链接：https://vjudge.net/problem/UVALive-3708

这道题的思路也是比较难想。

首先根据上一题（Uva 11300）可知，要想让移动距离最短，那么至少要使一个雕塑位置不变，随便一个即可。然后以它为坐标原点，以逆时针为正方向，钦定每一个雕塑的新位置。

然后我们设$pos$，那么可得到等式：

$\frac{i}{n} =\frac{pos}{n+m} <=> pos=i\times (n+m)\div n$

然后累加移动距离：

（移动距离=移动 / 总的距离）

移动距离=$|pos-floor(pos+0.5)|\div (n+m)$

这里的距离是按比例缩小之后的距离，接下来把每个雕塑移动到离它最近的位置，然而不可能出现“人多坑少”的情况。（证明详细见 蓝书P9）

（注意四舍五入：$pos=floor(pos+0.5)$

AC代码：

 #include<cstdio>

 #include<iostream>

 #include<cmath>

 using namespace std;

 int n,m;

 double pos;

 int main(){

     while(scanf("%d%d",&n,&m)==){

         double ans=0.0;

         for(int i=;i<=n;i++){

             pos=(double)i/n*(n+m);

             ans+=abs(pos-floor(pos+0.5))/(n+m);

         }

         printf("%.4lf\n",ans*);

     }

     return ;

 }

AC代码

相关文章