2325 Stars ——二分思想的应用.ppt
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_05.gif)
《2325 Stars ——二分思想的应用.ppt》由会员分享,可在线阅读,更多相关《2325 Stars ——二分思想的应用.ppt(45页珍藏版)》请在得力文库 - 分享文档赚钱的网站上搜索。
1、2352 Stars,谢 迪,2352 Stars 题目描述,Cartesian coordinatesLevel: an amount of the stars that are not higher and not to the right of the given star Task: Count the amounts of the stars of each level on a given map,3 1 0 1 2,2352 Stars 输入,Number of stars:N(1 = N = 15000)Coordinates of stars: 0=Xi,Yi=32000 T
2、here can be only one star at one point of the plane. Stars are listed in ascending order of Y coordinate. Stars with equal Y coordinates are listed in ascending order of X coordinate.,Input:NX1 Y1X2 Y2XN YN,This problem has huge input data,use scanf() instead of cin to read data to avoid time limit
3、exceed.,2352 Stars 输出,The first line contains amount of stars of the level 0, the second does amount of stars of the level 1 and so on, the last line contains amount of stars of the level N-1.,Output:C0C1Cn-1,2352 Stars Statistics,Total Submits 274 Accepted 58 Time Limit Exceed 96 Wrong Answer 69 Ru
4、ntime Error 10 Output Limit Exceed 8 Compile Error 33,算法一:原始想法,题目意思很简单我们就照着它说的按部就班的做吧把它当作模拟题for(i=0;in;i+) int tmp=0;for(j=0;ji;j+) if(xj=xi) / 统计不在右边的星星:因为题目已经 tmp+; / 保证输入的是按照y排好序的,因此numtmp+; / ji保证了统计的是不在上面的星星,算法一:原始想法,for(i=0;in;i+) int tmp=0;for(j=0;ji;j+) if(xj=xi) / 统计不在右边的星星:因为题目已经 tmp+; / 保
5、证输入的是按照y排好序的,因此numtmp+; / ji保证了统计的是不在上面的星星,Submit,Accepted 208K 4653MS C+ 0.39K 2005-04-07 21:54:47162.105.81.210/JudgeOnline,Time Limit Exceed C+ 0.39K 2005-04-07 22:51:26 A Submits 274 Accepted 58 Time Limit Exceed 96 + 1Wrong Answer 69 Runtime Error 10 Output Limit Exceed 8 Compile Error 33,算法二:另
6、一种原始的想法,题目意思很简单我们来换一个角度试试可能会有所收获我们设置m个桶(Buckets),m的范围为星星的x坐标的范围:0-32000!然后将所有的星星按输入顺序扔入桶中:记录在这个桶的位置上星星的个数扔入之前,先从0位置开始到这个星星的x位置,统计星星的个数,即求出了这个星星的level。,算法二:另一种原始的想法,这样做效率显然不高在算法一中,我们计算某个星星的level的时候,仅要考察它前面的全部星星,这样做的效率是:O(N*(N+1)/2),N的范围是1-15000。而在这个算法中,计算某个星星的level的时候,需要考察它所有的前面位置。复杂度为O(N*M)。而M的范围是0-
7、32000。比算法一还要烂!,for (i = 0; i n; i+)scanf(%d%d, ,算法三:由算法二想起的,这样做效率显然不高我们再来观察一下我们的算法二:我们每次计算一个星星的level的时候,总要对前面所有的位置都扫描一遍,时间都浪费在这里了!如果前面减少几个桶就好了!,for (i = 0; i n; i+)scanf(%d%d, ,算法三:由算法二想起的,如果前面减少几个桶就好了!我们可以把几个桶合并成一个大桶!计算的时候我们先考察在当前星星位置前面的大桶,再考察大桶和当前星星位置之间的小桶(包括当前位置)。图中我们把每3个小桶合并为一个大桶则我们可以很容易计算红色星星le
8、vel为13,11,2,算法三:由算法二想起的,则我们可以很容易计算红色星星level为13我们花的代价只是:统计3个大桶和2个小桶!而以前要统计11个小桶!3 + 2 11这个办法好!,11,2,算法三:由算法二想起的,是不是就取个小桶合并成一个大桶?当m达到30000时,大桶的个数也有10000了!显然效率不高!那我们取200个小桶合并成一个大桶,这样最多只有150个大桶。最坏情况下只用统计200+150=350次!,11,2,算法三:由算法二想起的,其实为了使平均效率比较高,我们得要大桶的个数和每个大桶包含的小桶的个数相同!即都为sqrt(m)个为什么?这样分散了“风险”!因为我们统计的
9、次数为:当前星星之前的所有大桶当前星星和最后一个大桶之间的小桶(包括当前位置)所以需要统计的次数不超过sqrt(m)+sqrt(m),11,2,算法三:由算法二想起的,#include #include const int CAPACITY = 200;const int MAX = 32000 + 1;const int BUCKET = MAX / CAPACITY + 1;const int N = 15000;short bucketBUCKET = 0;short aMAX = 0, levelN = 0;,/每个大桶相当于多少小桶,即大桶“容量”/最大位置/桶的个数/星星的个数/大
10、桶/ a 表示小桶,level 表示各个等级星星的个数,算法三:由算法二想起的,int main() int i, j, n, x, y, big, s; scanf(%d, ,/Big:当前位置之前大桶的个数 / s累计当前星星的level /首先计算大桶/然后计算小桶/当前星星所属大桶小桶均加,算法三:由算法二想起的,搞定了!回顾一下:时间复杂度 O(n*sqrt(m)空间复杂度 O(m),Submit,11 392257 xiedi 120K 90MS C+ 0.59K 2005-03-30 22:20:38 A Input中的数据来说明:图中红色数字即为f值。,算法四:有点点难度的,则
11、算法为:从根结点开始向下遍历,当不是叶结点时:若星星位置在当前结点的左侧,则:当前结点f值加1。访问左子树。若星星位置在当前结点的右侧,则:星星总数加上当前结点的f值,访问右子树。,当为叶结点时:星星总数加上当前结点f值,然后当前结点f值加1。,算法四:有点点难度的,举一个具体的例子:我们要计算图中红星星的level。,Total=,2,+2,+1,2,非叶结点:左侧:当前结点f值加1。访问左子树。右侧:星星总数加上当前结点的f值,访问右子树。,叶结点:星星总数加上当前结点f值,当前结点f值加1。,算法四:有点点难度的,另外一个例子:我们要计算图中红星星的level。,Total=,2,1,+
12、1,3,非叶结点:左侧:当前结点f值加1。访问左子树。右侧:星星总数加上当前结点的f值,访问右子树。,叶结点:星星总数加上当前结点f值,当前结点f值加1。,算法四:有点点难度的,怎样实现二叉树?由于本题中二叉树是满的,所以用数组实现就可以了。根结点标号为1;第二层顺次标为2,3;,则若当前结点为i,则其左子结点为i*2,其右子结点为i*2+1。,算法四:有点点难度的,#include #include const int MAXX = 32000;/最大范围int f(MAXX + 1) * 3;/f值int level15001;/记录各个level的星星个数,算法四:有点点难度的,int
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- stars 二分 思想 应用 利用 运用
![提示](https://www.deliwenku.com/images/bang_tan.gif)
限制150内