没有合适的资源?快使用搜索试试~ 我知道了~
二分原理的介绍,并介绍了二分原理的应用和特别注意事项
资源详情
资源评论
资源推荐
二分原理 收藏
作者:baihacker
来源:http://hi.baidu.com/feixue http://hi.csdn.net/baihacker
二分原理:
设 f 是定义在[a, b]上的 bool 函数,且满足性质若 f(i) = true 则 f(i+1) = true.
那么算法:
int l = a, r = b;
while (l <= r)
{
int mid = (l + r)/2;
if (f(mid)) r = mid - 1;
else l = mid + 1;
}
结束时一定有 l = r + 1;
那么有
l = b + 1 或者 l 是最小的使得 f 的值为 true 的数.
同时
r = a - 1 或者 r 是最大的使得 f 的值为 false 的数.
如果我们定义 f(a-1) = false;f(b+1) = true;
那么可以描述为
l 是最小的使得 f 的值为 true 的数.
r 是最大的使得 f 的值为 false 的数.
在有序的序列 x1,x2,x3,...,xn 找到 i,使得 xi >= value
根据上面的原理:
a = 1, b = 1;
f(i) = xi >= value;
这就是 stl 中的 lower_bound,类似地可以得到 upper_bound.
总之,二分原理可以求出满足单调性的函数的第一个满足某条件的值.
应用 1:
给定含有 n 个整数的序列,可以把这个序列分为 m 个子序列.
对于每个子序列,定义这个序列上的数的和为这个序列的权重.
所有子序列的权重中最大的称为这个划分的权重.
最小的划分权重是多大?
直接解决这个问题不好解决.
反过来思考,给定权重 x,最少可以划为多少份,这个问题可以用贪心算法解决.
定义 f(x) = 在权重 x 下最少的划分份数 <= m.
显然 x 太小的话,这个函数为假 false,x 够大的话,这个函数的值为 true.
找到第一个最少划分份数 <= m 的 x,显然有:
如果取 x-1,那么要至少分为大于 m 部分,不合要求.
gongzhi493712874
- 粉丝: 2
- 资源: 7
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功
评论0