地域劃分問題

題目描述：   

         現在有一塊長條形的土地，這個土地我們可以看成是由n塊小方格連接而成的(這些小方格我們可以將之編號為1到n)。而我們需要將其劃分成兩個部分，分別種上不同的作物(即作物A和B)，劃分必須在某兩個小方格之間進行，或者在土地的最左端或最右端，若劃分在第i塊到第i+1塊間進行，則劃分后，第1至第i塊地種A，剩下的地種B。現在有一些專家對土地進行了檢測，他們每個人評估了每塊土地適合種的作物。請你找到一個合適的劃分，使得其與所有專家的評估最吻合，也就是說，你劃分到A而專家評估為B的次數和你劃分到B而專家評估為A的次數之和最小。

輸入描述:

每組數據給定一個專家評估表land(其中0為評估A，1為評估B)，以及小塊數量n(1≤n≤300)，專家評估次數m(1≤m≤300)

輸出描述:

請返回你的劃分,即i和i+1。若在最左端，則輸出0，1；不吻合在最右端則輸出n,n+1。若有多解輸出最靠左的劃分。

輸入例子:

[[1,1,1,1],[0,0,0,0],[1,0,1,1]],4,3

輸出例子:

[0,1]

方法聲明：

vector<int> getPartition(const vector<vector<int> >& land, int n, int m) 
    {
        // write code here
    }

分析：

            根據題目要求，我們需要找到一個邊界，這個邊界的左邊都為 0 ，右邊都為 1 ，而且，這個劃分必須與專家評估的結果不同的土地（也就是方格）數最少，

如下示例：    

輸入：

[[1,1,1,1],[0,0,0,0],[1,0,1,1]],4,3

也就是 4 塊土地，3次評估

則所有的情況如下圖：

將每種情況對應的專家評估不吻合的土地數加起來：

遇到不吻合的土地數相同的情況下（如上面 1111 和 0011），取最左的劃分，也就是 1111，則劃分為 0,1

再舉一個例子：

所有情況如下：

所以劃分就為： 1 , 2

根據上述思想，寫代碼就容易多了：

vector<int> getPartition(const vector<vector<int> >& land, int n, int m)
{
	int* a = new int[n];
	for (int i = 0; i < n; ++i)  //全部置1，從全 1 的情況開始
	{
		a[i] = 1;
	}

	int left = 0;		//劃分的左邊界
	int right = 1;      //計劃分的右邊界
	int mindif = n*m;   //最少的不吻合的土地數
	int difCount = 0;   //用來記錄不吻合的個數
	int zeroCount = 0;  //劃分序列中 0 的個數
	int dif = 0;        //每種情況的不吻合的土地數
	for (int index = 0; index < n + 1; ++index)  //一共有n+1種可能組合
	{
		for (int i = 0; i < m; ++i)
		{
			for (int j = 0; j < n; ++j)
			{
				if (land[i][j] != a[j])
					++difCount;
			}
			dif += difCount;
			difCount = 0;
		}

		if (dif <= mindif)
		{
			if (dif < mindif)
			{
				mindif = dif;
				left = zeroCount;
				right = zeroCount + 1;
			}
			else if (zeroCount < left)
			{
				left = zeroCount;
				right = zeroCount + 1;
			}
		}
		
		dif = 0;

		if (zeroCount < n)
			a[zeroCount++] = 0;
	}

	delete[] a;
	a = NULL;

	vector<int> ret;
	ret.push_back(left);
	ret.push_back(right);

	return ret;
}