BNUOJ 34982 Beautiful Garden

题目地址:BNUOJ 34982

题意：
看错题意纠结了好久。。。
在坐标轴上有一些树，现在要重新排列这些树，使得相邻的树之间间距相等。
刚开始瞄了一眼以为是求最短的移动距离...后来发现是求最少去移动的树的数量。

分析：
刚开始想错了，以为任意取两棵树，作为相邻的两棵树就行了，吃了好多个wa后，发现这个有问题，因为考虑里面三棵树为最终序列中的三个，那么就有可能判断不出来。
于是想了新的方法，枚举两棵树后，再枚举中间有几棵树，在两棵树中间找有几棵树不用移动。
具体见代码。

代码：

/*
*  Author:      illuz 
  
   
*  File:        b.cpp
*  Create Date: 2014-05-29 14:43:59
*  Descripton:   
*/

#include 
   
     #include 
    
      #include 
     
       #include 
      
        #include 
       
         #include 
        
          using namespace std; typedef long long ll; const int N = 44; const double EPS = 1e-8; ll t, n, x[N], mmin; set
         
           s; void deal(int lhs, int rhs) { int cnt; ll dis = x[rhs] - x[lhs]; // 如果在同一点就作为间距为0的情况处理 if (dis == 0) { mmin = min(mmin, n - (rhs - lhs + 1)); return; } // 枚举lhs和rhs中有k个间距，也可以枚举树 for (int k = 2; k < n; k++) { cnt = 2; // 在中间的树中找要不用移动的树 for (int i = lhs + 1; i < rhs; i++) { if (x[i] != x[i - 1] && x[i] > x[lhs] && x[i] < x[rhs] && (x[i] - x[lhs]) * k % dis == 0) cnt++; } mmin = min(mmin, n - cnt); } } int main() { cin >> t; for (int cas = 1; cas <= t; cas++) { cin >> n; s.clear(); for (int i = 0; i < n; i++) { cin >> x[i]; } if (n <= 2) { printf("Case #%d: 0\n", cas); continue; } mmin = N; sort (x, x + n); for (int i = 0; i < n; i++) { for (int j = i + 1; j < n; j++) { deal(i, j); } } printf("Case #%d: ", cas); cout << mmin << endl; } return 0; }