开发者社区> 华山青竹> 正文

二分法小结

简介: 文章来源:http://www.cnblogs.com/hyl2000/p/5734908.html NOIP中二分应该是很简单的算法了,去年noip的day2-t1就是裸的二分,这里有两个例题   1、poj2456:Farmer John has built a new long barn, w...
+关注继续查看

文章来源:http://www.cnblogs.com/hyl2000/p/5734908.html

NOIP中二分应该是很简单的算法了,去年noip的day2-t1就是裸的二分,这里有两个例题

  1、poj2456:Farmer John has built a new long barn, with N (2 <= N <= 100,000) stalls. The stalls are located along a straight line at positions x1,...,xN (0 <= xi <= 1,000,000,000). His C (2 <= C <= N) cows don't like this barn layout and become aggressive towards each other once put into a stall. To prevent the cows from hurting each other, FJ want to assign the cows to the stalls, such that the minimum distance between any two of them is as large as possible. What is the largest minimum distance?(大意就是说有一些牛和牛舍,我们要尽量使最近的两头牛之间的距离最大)

  2、跳石头(noip2015-day2-t1):每年奶牛们都要举办各种特殊版本的跳房子比赛,包括在河里从一个岩石跳到另一个岩石。这项激动人心的活动在一条长长的笔直河道中进行,在起点和离起点L远 (1 ≤ L≤ 1,000,000,000) 的终点处均有一个岩石。在起点和终点之间,有N (0 ≤ N ≤ 50,000) 个岩石,每个岩石与起点的距离分别为Di (0 < Di < L)。在比赛过程中,奶牛轮流从起点出发,尝试到达终点,每一步只能从一个岩石跳到另一个岩石。当然,实力不济的奶牛是没有办法完成目标的。农夫约翰为他的奶牛们感到自豪并且年年都观看了这项比赛。但随着时间的推移,看着其他农夫的胆小奶牛们在相距很近的岩石之间缓慢前行,他感到非常厌烦。他计划移走一些岩石,使得从起点到终点的过程中,最短的跳跃距离最长。他可以移走除起点和终点外的至多(0 ≤ M ≤ N) 个岩石。请帮助约翰确定移走这些岩石后,最长可能的最短跳跃距离是多少?(简单来说就是使最小值最大)

  这类问题有个明显的特征:使最小值最大或者使最大值最小。这个时候大概步骤就是先对读进来的数据进行排序(因为二分查找是在有序的数据上进行的)然后执行二分。其中二分里的check函数是最关键的部分,例如第一题中我们就是二分答案,然后在check中贪心的来安排牛的位置,看是否能够满足答案。而第二题也是二分答案,check中按我们求出的答案把不满足答案的石头撤掉,看是否能够满足答案。这就是check的大概思路:即检查是否能够满足答案。

  二分中还有一个重要的细节:求最大值的最小值时mid=(l+r)/2,l=mid+1,r=mid;而查找最小值的最大值时mid=(l+r+1)/2,l=mid,r=mid-1。不然程序会陷入死循环,或者得不到正确答案。

  最后一点就是实数二分的时候因为精度需要常常我们会让程序一直进行计算,然而由于计算时的精度误差,常常也会使程序效率低下或者死循环。一般来讲我们这时可以限制二分次数,一般60-70次即可满足精度需要,这样可以提高程序效率,避免TLE的情况出现。

  最最后一点,这类问题数据量一般都非常大,记得用scanf读入,第一题我就因为用cin而TLE了,改成scanf之后马上就过了。。。。。

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

相关文章
如何设置阿里云服务器安全组?阿里云安全组规则详细解说
阿里云安全组设置详细图文教程(收藏起来) 阿里云服务器安全组设置规则分享,阿里云服务器安全组如何放行端口设置教程。阿里云会要求客户设置安全组,如果不设置,阿里云会指定默认的安全组。那么,这个安全组是什么呢?顾名思义,就是为了服务器安全设置的。安全组其实就是一个虚拟的防火墙,可以让用户从端口、IP的维度来筛选对应服务器的访问者,从而形成一个云上的安全域。
19079 0
阿里云服务器ECS登录用户名是什么?系统不同默认账号也不同
阿里云服务器Windows系统默认用户名administrator,Linux镜像服务器用户名root
15765 0
阿里云服务器如何登录?阿里云服务器的三种登录方法
购买阿里云ECS云服务器后如何登录?场景不同,阿里云优惠总结大概有三种登录方式: 登录到ECS云服务器控制台 在ECS云服务器控制台用户可以更改密码、更换系.
28300 0
阿里云ECS云服务器初始化设置教程方法
阿里云ECS云服务器初始化是指将云服务器系统恢复到最初状态的过程,阿里云的服务器初始化是通过更换系统盘来实现的,是免费的,阿里云百科网分享服务器初始化教程: 服务器初始化教程方法 本文的服务器初始化是指将ECS云服务器系统恢复到最初状态,服务器中的数据也会被清空,所以初始化之前一定要先备份好。
16601 0
阿里云服务器安全组设置内网互通的方法
虽然0.0.0.0/0使用非常方便,但是发现很多同学使用它来做内网互通,这是有安全风险的,实例有可能会在经典网络被内网IP访问到。下面介绍一下四种安全的内网互联设置方法。 购买前请先:领取阿里云幸运券,有很多优惠,可到下文中领取。
22183 0
阿里云服务器如何登录?阿里云服务器的三种登录方法
购买阿里云ECS云服务器后如何登录?场景不同,大概有三种登录方式:
13205 0
+关注
华山青竹
一个喜欢玩代码的小青年呵呵呵
543
文章
0
问答
文章排行榜
最热
最新
相关电子书
更多
JS零基础入门教程(上册)
立即下载
性能优化方法论
立即下载
手把手学习日志服务SLS,云启实验室实战指南
立即下载