标签 (空格分隔): 课堂笔记
二分复杂度 logN
应用:
1, 求零点
2, 求一堆东西中的最小值的最大是多少 (二分答案)
实现时候注意整数的整除和实数的精确范围.
例题:
1, 派
我的生日要到了! 根据习俗, 我需要将一些派分给大家. 我有 N 个不同口味, 不同大小的派. 有 F 个朋友会来参加我的派对, 每个人会拿到一块派 (必须一个派的一块, 不能由几个派的小块拼成; 可以是一整个派).
我的朋友们都特别小气, 如果有人拿到更大的一块, 就会开始抱怨. 因此所有人拿到的派是同样大小的 (但不需要是同样形状的), 虽然这样有些派会被浪费, 但总比搞砸整个派对好. 当然, 我也要给自己留一块, 而这一块也要和其他人的同样大小.
请问我们每个人拿到的派最大是多少? 每个派都是一个高为 1, 半径不等的圆柱体.
二分答案
扫一遍派, 检验够不够分, 看看一共分出多少分, 比 F+1 多就往右, 少就往左.
答案区间:[0, 派的总体积比人数]
2, 抽干水塘
公园里有 n 个水塘, 需要把这 n 个水塘中的水排干, 水塘中的水在自然条件下 1 个单位的时间可以蒸发 A 升水. 现在买了 1 台抽水机, 使用抽水机可以让你用 1 个单位的时间使每个水塘除开自然蒸发的 A 升水外, 还可抽 B 升水, 但在 1 个单位的时间内只能对 1 个水塘使用.
要你求出排干所有水塘的最少时间 (水塘中的水为 0 时为排干)
二分时间,
答案区间 [0, 个人认为是最大池塘蒸发所用时间 (老师说大点也没事二分快)]
检验答案, 看蒸发 A 的体积能把哪些池塘蒸干,
然后将剩余的池塘用水抽干, 需要多长时间
注意每个单位时间只能抽一个池塘
3, 序列积第 m 小元素
给出两个长度为 n 的数组 A 和 B, 在 A 和 B 中各任取一个, 可以得到 n*n 个积. 求第 m 小的元素.
n<=100000
二分答案
先排个序 (sort 一下)
首先按顺序枚举 i,
固定 \(a_i\) 之后, 看有多少个 b 的元素满足 \(a_i\)*\(b_i\)<=x(x 为二分的答案, 就是一个乘积)
复杂度 nlognlogm
优化: 双指针. 复杂度 nlogm, 因为 i 和 j 是满足 j 随 i 增加而减小的关系的
- bool check(int x)
- {
- int cnt = 0;
- int j = n;
- for(int i = 1; i <= n; i++){
- while(j>0&&b[j]*a[i]>x)
- j--;
- //i 在增大时 j 一定会减小, 所以在 i 时可以从 i-1 的 j 时枚举 j
- cnt+=j;
- }
- return cnt>=m;
- }
几道 noip 真题
NOIP2015 跳石头 https://www.luogu.com.cn/problem/P2678
- poj2728 Desert King http://poj.org/problem?id=2728
- poj 2976 Dropping tests http://poj.org/problem?id=2976
来源: http://www.bubuko.com/infodetail-3384462.html