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;
}