uva - UVA 1388 - Graveyard (數學推理）

題意：有一個周長為10000的圓上等距分布著n個雕塑，現在又加入m個雕塑，位置隨意，希望n+m個雕塑仍然均勻分布。這就要移動其中一些雕像，求移動的最小距離。

方法：仍然是劉大大的例題，假定某一個雕像不動，作為坐標原點，其他雕像按照逆時針標上到原點的距離標號。不是真是距離而是按比例縮小後的。接下來移動到離它最近的位置，例題用了四捨五入，感覺是不對的，例如x = 0.5， y = 1.499999，但是x和y的差還是小於1，而相鄰雕像的距離才為1，所以這樣看也是可行的。

注意：floor和四捨五入的寫法。

#include   
#include   
#include   
#include   
#include   
#include   
#include   
#include   
#include   

using namespace std;

int main()  
{  
#ifdef Local    
	freopen("a.in", "r", stdin);    
#endif
	int n = 0, m = 0, i = 0;
	while (cin >> n >> m)
	{
		double ans = 0.0;
		for (i = 1; i < n; i++)
		{
			double pos = (double)i/n * (n+m);
			ans += fabs(pos - floor(pos+0.5)) / (n+m);
		}
		cout << setprecision(4) << fixed << ans*10000 << endl;
	}
}

要求嚴謹的話，應該和前後兩個位置比較距離，取小的那個，這裡貼上一位仁兄的代碼，我就偷懶啦。

來自：http://blog.csdn.net/mr_zys/article/details/17270885

#include 
#include 
#include 
const double len = 10000;
int n,m;
double d0,d1;
int main()
{
  while(~scanf("%d%d",&n,&m)) {
    if(m % n == 0) printf("0.0\n");
    else {
      d0 = len / (n * 1.0);
      d1 = len / ((n + m) * 1.0);
      double ans = 0.0;
      for(int i = 1; i < n; i++) {
	double t = i * d0;
	int d = floor(t/d1);
	double t1 = fabs(t - d * d1);
	double t2 = fabs(t - (d + 1.0) * d1);
	if(t1 > t2) ans += t2;
	else ans += t1;
      }
      printf("%.4lf\n",ans);
    }
  }
  return 0;
}