墓地雕塑
題目描述:
在一個周長為10000的圓上等距分布著n個雕塑。現在又有m個新雕塑加入(位置可以隨意放),希望所有n+m個雕塑在圓周上均勻分布。這就需要移動其中一些原有的雕塑。要求n個雕塑移動的總距離盡量小。
輸入格式:
輸入包含若干組數據。每組數據僅一行,包含兩個整數n和m(2<=n<=1000, 1<=m<=1000),即原始的雕塑數量和新加的雕塑數量。輸入結束標志為文件結束符(EOF)。
輸出格式:
輸入僅一行,為最小總距離,精確到0.0001。
樣例輸入:
2 1
2 3
3 1
10 10
1666.6667
1000.0
1666.6667
0.0
解:此題可假設某一點為原點,其它點按比例縮小,與原來的點進行比較,並移動到較近的位置~
#include#include int main() { int n, m; while(scanf("%d%d", &n, &m) == 2) { double ans = 0.0, pos = 0.0; for(int i = 1; i < n; i++) { pos = (double)i / n * (n+m); //計算每個需要移動的雕塑的坐標(成比例縮小,目的是通過與floor作差得到移動距離~) ans += fabs(pos-floor(pos+0.5)) / (n+m);//累加移動距離 } printf("%.4lf\n", ans*10000); //等比例擴大坐標 } return 0; }
運行結果: