地域划分问题-创新互联
题目描述:
我们提供的服务有:成都网站建设、网站设计、微信公众号开发、网站优化、网站认证、红桥ssl等。为成百上千企事业单位解决了网站和推广的问题。提供周到的售前咨询和贴心的售后服务,是有科学管理、有技术的红桥网站制作公司现在有一块长条形的土地,这个土地我们可以看成是由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]
方法声明:
vectorgetPartition(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
根据上述思想,写代码就容易多了:
vectorgetPartition(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; }
创新互联www.cdcxhl.cn,专业提供香港、美国云服务器,动态BGP最优骨干路由自动选择,持续稳定高效的网络助力业务部署。公司持有工信部办法的idc、isp许可证, 机房独有T级流量清洗系统配攻击溯源,准确进行流量调度,确保服务器高可用性。佳节活动现已开启,新人活动云服务器买多久送多久。
网页名称:地域划分问题-创新互联
文章路径:http://myzitong.com/article/diesss.html