題目描述：   

我們提供的服務(wù)有：成都網(wǎng)站建設(shè)、網(wǎng)站設(shè)計(jì)、微信公眾號(hào)開發(fā)、網(wǎng)站優(yōu)化、網(wǎng)站認(rèn)證、紅橋ssl等。為成百上千企事業(yè)單位解決了網(wǎng)站和推廣的問題。提供周到的售前咨詢和貼心的售后服務(wù)，是有科學(xué)管理、有技術(shù)的紅橋網(wǎng)站制作公司

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

輸入描述:

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

輸出描述:

請(qǐng)返回你的劃分,即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 getPartition(const vector >& land, int n, int m) 
    {
        // write code here
    }

分析：

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

如下示例：    

輸入：

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

也就是 4 塊土地，3次評(píng)估

則所有的情況如下圖：

將每種情況對(duì)應(yīng)的專家評(píng)估不吻合的土地?cái)?shù)加起來：

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

再舉一個(gè)例子：

所有情況如下：

所以劃分就為： 1 , 2

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

vector getPartition(const vector >& 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;      //計(jì)劃分的右邊界
	int mindif = n*m;   //最少的不吻合的土地?cái)?shù)
	int difCount = 0;   //用來記錄不吻合的個(gè)數(shù)
	int zeroCount = 0;  //劃分序列中 0 的個(gè)數(shù)
	int dif = 0;        //每種情況的不吻合的土地?cái)?shù)
	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 ret;
	ret.push_back(left);
	ret.push_back(right);

	return ret;
}

創(chuàng)新互聯(lián)www.cdcxhl.cn，專業(yè)提供香港、美國云服務(wù)器，動(dòng)態(tài)BGP最優(yōu)骨干路由自動(dòng)選擇，持續(xù)穩(wěn)定高效的網(wǎng)絡(luò)助力業(yè)務(wù)部署。公司持有工信部辦法的idc、isp許可證， 機(jī)房獨(dú)有T級(jí)流量清洗系統(tǒng)配攻擊溯源，準(zhǔn)確進(jìn)行流量調(diào)度，確保服務(wù)器高可用性。佳節(jié)活動(dòng)現(xiàn)已開啟，新人活動(dòng)云服務(wù)器買多久送多久。

網(wǎng)站題目：地域劃分問題-創(chuàng)新互聯(lián)
網(wǎng)頁路徑：http://weahome.cn/article/diesss.html