地域划分问题

题目描述:   地域划分问题

光明网站建设公司创新互联,光明网站设计制作,有大型网站制作公司丰富经验。已为光明近1000家提供企业网站建设服务。企业网站搭建\外贸网站制作要多少钱,请找那个售后服务好的光明做网站的公司定做!

         现在有一块长条形的土地,这个土地我们可以看成是由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 getPartition(const vector >& 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 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;      //计划分的右边界
	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 ret;
	ret.push_back(left);
	ret.push_back(right);

	return ret;
}


分享题目:地域划分问题
文章源于:http://scyanting.com/article/jhsgoo.html