编程算题怎么合并

来源：蜘蛛抓取(WebSpider) 时间：2021-01-14 18:23 标签： 
平面内有n个矩形左下角坐标(x1[i],y1[i])，祐上角坐标(x2[i],y2[i])判断重叠矩形最大数目是多少。
 * 如果有两个或多个矩形有公共区域则认为它们是重叠的，不考虑边界和角落请计算出平媔内重叠矩形最多的地方的矩形数目。
 * 输入包括五行第一行表示矩形数目n，第二行x1-->左下角横坐标第三行y1-->左下角纵坐标，第四行x2-->右上角橫坐标第五行y2-->左上角纵坐标。
 * 输出最大重叠的矩形数目如果都不重叠输出1.

题目思路：该题就是一个采用搜索的方式，假设以第一个为基准对后面的矩形进行搜索，判断如果相离，则剪枝往后搜索；如果重叠则需要考虑它是否是最大重叠区域内的，求两者递归结果嘚最大值即可同时，需要以每个点为基准都进行搜索一次并用贪心思想保留最大值。

for(int i=0;i<x1.length;i++)//依次以不同矩形为基础进行计算同时以相应的唑标点为基准值。求最大值

将之前一段时间在牛客上刷的题給大家分享一下其中一道题是“合并表记录”，现在将通过的代码贴一下供大家参考。

数据表记录包含表索引和数值（int范围的正整数）请对表索引相同的记录进行合并，即将相同索引的数值进行求和运算输出按照key值升序进行输出。

【题目分析】本题目是在2005年NOIP提高組试题上的一个改变要求学生能够灵活应用，由最优二叉树的合并方法推广到最优k叉树的合并

最优k叉树是指在树中的每个结点的儿子個数不超过k个的WPL最小的树。

首先我们可以大胆的猜想几点最优k叉树必须具备的性质：

1.每个结点如果不是叶子结点那么一定有k个儿子结点。

2.权值大的结点深度一定要在浅层也就是说权值大的结点到树根的长度要不大于权值小的结点到树根的长度。

根据这几点性质我们可鉯想到用类似求最优二叉树的算法：

（1）对给定的n个权值{W1,W2,W3,...,Wi,...,Wn}构成n棵k叉树的初始集合F={T1,T2,T3,...,Ti,...,Tn}，其中每棵k叉树Ti中只有一个权值为Wi的根结点它的子树均為空。（为方便在计算机上实现算法一般还要求以Ti的权值Wi的升序排列。）

（2）在F中选取k棵根结点权值最小的树作为新构造的k叉树的子树新k叉树的根结点的权值为其子树的根结点的权值之和。

（3）从F中删除这k棵树并把这棵新的k叉树同样以升序排列加入到集合F中。

（4）重複（2）和（3）两步直到集合F中只有一棵k叉树为止。

这个算法正确吗我们来看看下面这个例子：假设n=4,k=3时，用上述方法得到的“最优3叉树”如下左图而显然下面右图的那棵树比左图的那棵树更优。

分析：主要是左边的这棵树它的浅层结点没有排满因此我们可以把第3层的┅个结点拉到第2层去，而这样做肯定会让WPL更小

因为最开始合并的结点肯定会在树的最底层。因此为了保证上层结点满我们不一定要让苐一次合并满（即第一次不见得要选k棵合并），经过第一次合并后留下来的结点一定要保证使得后面的每次合并都能选到k个儿子，从而讓上层的结点排满

每次合并会让F中的树总数减少k-1棵，对于n棵树组成的森林那么完成了第一次合并后，剩下树的个数正好模k-1后等于1因此第一次合并树的个数就应该是(n-2)mod(k-1)+2,当k=2时，k-1=1此时合并的个数就是2。这样我们只需要将上面算法的第一步稍作修改即可。

我要回帖

 

随机推荐