墓地 sculpture设置。在周长为1.1.4×1e4的圆周上均匀放置了n座墓地 sculpture。现计划增加m座新的墓地 sculpture以确保最终布局依然均匀。

阅读量：

墓地雕塑

题目来源：《算法竞赛入门经典——训练指南》/刘汝佳，陈锋编著

在周长为10000的圆形轨道上，均匀排列着n座雕塑。现计划新增m座雕塑（其摆放位置可自由选择），目标是使所有n+m座雕塑在圆周上实现等距分布。这一过程可能需要对部分原有雕塑进行位置调整。
要求所有被移动的原有雕塑所行进的总路径长度达到最小值。
【输入格式

示例代码展示

复制代码

    //代码来源：《算法竞赛入门经典——训练指南》/刘汝佳，陈锋编著.一北京：清华大学出版社，2012.9
    
    #include<cstdio>
    #include<cmath>
    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 += fabs(pos - floor(pos + 0.5)) / (n+m); //累加移动距离
    		}

全部评论 (0)

还没有任何评论哟~