二分查找与前缀和练习（二）
文章目录
题目来自洛谷题单【算法1-6】二分查找与二分答案
P2249 【深基13.例1】查找
题目描述
输入 $n$ 个不超过 $10^9$ 的单调不减的（就是后面的数字不小于前面的数字）非负整数 $a_1,a_2,\dots,a_{n}$，然后进行 $m$ 次询问。对于每次询问，给出一个整数 $q$，要求输出这个数字在序列中第一次出现的编号，如果没有找到的话输出 $-1$ 。
输入格式
第一行 $2$ 个整数 $n$ 和 $m$，表示数字个数和询问次数。
第二行 $n$ 个整数，表示这些待查询的数字。
第三行 $m$ 个整数，表示询问这些数字的编号，从 $1$ 开始编号。
输出格式
输出一行，$m$ 个整数，以空格隔开，表示答案。
输入输出样例 #1
输入 #1
111 3
21 3 3 3 5 7 9 11 13 15 15
31 3 6
输出 #1
11 2 -1
说明/提示
数据保证，$1 \leq n \leq 10^6$，$0 \leq a_i,q \leq 10^9$，$1 \leq m \leq 10^5$
本题输入输出量较大，请使用较快的 IO 方式。
题解
查找大于等于某一值的第一个元素。Python 会 MLE。
1#define _CRT_SECURE_NO_WARNINGS
2
3#include <cstdio>
4
5const int N = 1e6 + 5;
6int n, q, nums[N] = { 0 }, k;
7
8int main() {
9 scanf("%d%d", &n, &q);
10 for (int i = 0; i < n; i++) {
11 scanf("%d", &nums[i]);
12 }
13 for (int i = 0; i < q; i++) {
14 scanf("%d", &k);
15 int l = 0, r = n - 1, mid;
16 while (l < r) {
17 mid = (l + r) >> 1;
18 if (nums[mid] >= k) {
19 r = mid;
20 }
21 else {
22 l = mid + 1;
23 }
24 }
25 printf("%d ", nums[l] == k ? l + 1 : -1);
26 }
27 return 0;
28}
P1102 A-B 数对
题目背景
出题是一件痛苦的事情！
相同的题目看多了也会有审美疲劳，于是我舍弃了大家所熟悉的 A+B Problem，改用 A-B 了哈哈！
题目描述
给出一串正整数数列以及一个正整数 $C$，要求计算出所有满足 $A - B = C$ 的数对的个数（不同位置的数字一样的数对算不同的数对）。
输入格式
输入共两行。
第一行，两个正整数 $N,C$。
第二行，$N$ 个正整数，作为要求处理的那串数。
输出格式
一行，表示该串正整数中包含的满足 $A - B = C$ 的数对的个数。
输入输出样例 #1
输入 #1
14 1
21 1 2 3
输出 #1
13
说明/提示
对于 $75%$ 的数据，$1 \leq N \leq 2000$。
对于 $100%$ 的数据，$1 \leq N \leq 2 \times 10^5$，$0 \leq a_i <2^{30}$，$1 \leq C < 2^{30}$。
2017/4/29 新添数据两组
题解
首先对原数列排序并遍历 $B$，然后二分查找数列中首个等于 $B+C$ 的位置（如果没有就跳过），再查找数列中首个大于等于 $B+C+1$ 的位置，两个位置做差就是数列中 $B+C$ 的数量，同时存储每个 $B$ 对应的 $A$ 的数量避免重复计算。如果 $B+C$ 是数列中的最大值则有可能搜不到 $B+C+1$ 的位置，因此需要在排好序的数列后再加一个更大的元素。
1from collections import defaultdict
2
3n, c = map(int, input().strip().split())
4nums = list(map(int, input().strip().split()))
5nums.sort()
6nums += [nums[-1] + 1]
7
8count = 0
9memo = defaultdict(lambda: -1)
10for i in range(n):
11 if memo[nums[i]] != -1:
12 count += memo[nums[i]]
13 continue
14
15 l = 0
16 r = n - 1
17 target = nums[i] + c
18 l, r = 0, n - 1
19 while l < r:
20 mid = (l + r) >> 1
21 if nums[mid] >= target:
22 r = mid
23 else:
24 l = mid + 1
25
26 if nums[l] == target:
27 lb = l
28 else:
29 memo[nums[i]] = 0
30 continue
31
32 l = 0
33 r = n
34 while l < r:
35 mid = (l + r) >> 1
36 if nums[mid] >= target + 1:
37 r = mid
38 else:
39 l = mid + 1
40 memo[nums[i]] = l - lb
41 count += memo[nums[i]]
42print(count)
使用 bisect 模块：
1from collections import defaultdict
2from bisect import bisect_left as b_l
3
4n, c = map(int, input().strip().split())
5nums = list(map(int, input().strip().split()))
6nums.sort()
7nums += [nums[-1] + 1]
8
9count = 0
10memo = defaultdict(lambda: -1)
11for num in nums:
12 if memo[num] != -1:
13 count += memo[num]
14 continue
15
16 target = num + c
17 idx = b_l(nums, target)
18
19 if idx < n and nums[idx] == target:
20 lb = idx
21 else:
22 memo[num] = 0
23 continue
24
25 idx = b_l(nums, target + 1)
26 memo[num] = idx - lb
27 count += idx - lb
28print(count)
bisect.bisect_right 用于找出列表中第一个大于 $x$ 的下标，bisect.bisect_left 用于找出列表中第一个大于等于 $x$ 的下标。而且使用 bisect 模块进行二分查找前必须要有一个可迭代对象，也就是说每一项的值必须是明确的。如果是浮点数的二分查找就不能用 biscet 解决，此外像三体攻击这样数据量过大无法一次性全部计算好，而要找到元素位置后再计算的情况就不能使用 bisect。当然如果不怕麻烦，可以自己定义一个可迭代对象并且重载 __getitem__ 魔法方法，以实现对元素的懒加载，但是这样的代码量还不如自己手搓二分。
另外这道题数据范围 $1\leq a_i\leq2^{30}$，肯定没法用前缀和做。
P1024 [NOIP 2001 提高组] 一元三次方程求解
题目描述
有形如：$a x^3 + b x^2 + c x + d = 0$ 这样的一个一元三次方程。给出该方程中各项的系数（$a,b,c,d$ 均为实数），并约定该方程存在三个不同实根（根的范围在 $-100$ 至 $100$ 之间），且根与根之差的绝对值 $\ge 1$。要求由小到大依次在同一行输出这三个实根(根与根之间留有空格)，并精确到小数点后 $2$ 位。
提示：记方程 $f(x) = 0$，若存在 $2$ 个数 $x_1$ 和 $x_2$，且 $x_1 < x_2$，$f(x_1) \times f(x_2) < 0$，则在 $(x_1, x_2)$ 之间一定有一个根。
输入格式
一行，$4$ 个实数 $a, b, c, d$。
输出格式
一行，$3$ 个实根，从小到大输出，并精确到小数点后 $2$ 位。
输入输出样例 #1
输入 #1
11 -5 -4 20
输出 #1
1-2.00 2.00 5.00
说明/提示
【题目来源】
NOIP 2001 提高组第一题
题解
浮点数前缀和，通过 l 与 r 的差控制精度。
1a, b, c, d = map(float, input().strip().split())
2
3
4def f(x):
5 return a * (x**3) + b * (x**2) + c * x + d
6
7
8ans = set()
9for i in range(-101, 101):
10 if f(i) * f(i + 1) <= 0:
11 if f(i) == 0:
12 ans.add(i)
13 if f(i + 1) == 0:
14 ans.add(i + 1)
15
16 if f(i) > 0 and f(i + 1) < 0:
17 l, r = i, i + 1
18 while r - l >= 0.001:
19 mid = (l + r) / 2
20 if f(mid) > 0:
21 l = mid
22 elif f(mid) < 0:
23 r = mid
24 else:
25 ans.add(mid)
26 break
27 ans.add(mid)
28
29 if f(i) < 0 and f(i + 1) > 0:
30 l, r = i, i + 1
31 while r - l >= 0.001:
32 mid = (l + r) / 2
33 if f(mid) > 0:
34 r = mid
35 elif f(mid) < 0:
36 l = mid
37 else:
38 ans.add(mid)
39 break
40 ans.add(mid)
41
42print(*map(lambda x: f"{x:.2f}", sorted(list(ans))))
P1678 烦恼的高考志愿
题目背景
计算机竞赛小组的神牛 V 神终于结束了高考，然而作为班长的他还不能闲下来，班主任老 t 给了他一个艰巨的任务：帮同学找出最合理的大学填报方案。可是 v 神太忙了，身后还有一群小姑娘等着和他约会，于是他想到了同为计算机竞赛小组的你，请你帮他完成这个艰巨的任务。
题目描述
现有 $m$ 所学校，每所学校预计分数线是 $a_i$。有 $n$ 位学生，估分分别为 $b_i$。
根据 $n$ 位学生的估分情况，分别给每位学生推荐一所学校，要求学校的预计分数线和学生的估分相差最小（可高可低，毕竟是估分嘛），这个最小值为不满意度。求所有学生不满意度和的最小值。
输入格式
第一行读入两个整数 $m,n$。$m$ 表示学校数，$n$ 表示学生数。
第二行共有 $m$ 个数，表示 $m$ 个学校的预计录取分数。第三行有 $n$ 个数，表示 $n$ 个学生的估分成绩。
输出格式
输出一行，为最小的不满度之和。
输入输出样例 #1
输入 #1
14 3
2513 598 567 689
3500 600 550
输出 #1
132
说明/提示
数据范围：
对于 $30%$ 的数据，$1\leq n,m\leq1000$，估分和录取线 $\leq10000$；
对于 $100%$ 的数据，$1\leq n,m\leq100000$，估分和录取线 $\leq 1000000$ 且均为非负整数。
题解
在分数线内二分查找学生分数所在的区间，然后看看学生分数和哪个离得近就加上哪个的差。如果学神考的太低或者太高则可能用二分查找找不到对应的区间，这时候就得特判。
1from collections import defaultdict
2
3m, n = map(int, input().strip().split())
4schools = list(map(int, input().strip().split()))
5students = tuple(map(int, input().strip().split()))
6schools.sort()
7
8memo = defaultdict(lambda: -1)
9count = 0
10for stu in students:
11 if memo[stu] != -1:
12 count += memo[stu]
13 continue
14
15 l, r = 0, m
16 while l < r:
17 mid = (l + r) >> 1
18 if schools[mid] >= stu:
19 r = mid
20 else:
21 l = mid + 1
22
23 if 0 < l < m:
24 diff = min(schools[l] - stu, stu - schools[l - 1])
25 elif l == 0:
26 diff = schools[l] - stu
27 else:
28 diff = stu - schools[-1]
29 memo[stu] = diff
30 count += diff
31
32print(count)
bisect 做法：
1from collections import defaultdict
2from bisect import bisect_left as b_l
3
4m, n = map(int, input().strip().split())
5schools = list(map(int, input().strip().split()))
6students = tuple(map(int, input().strip().split()))
7schools.sort()
8
9memo = defaultdict(lambda: -1)
10count = 0
11for stu in students:
12 if memo[stu] != -1:
13 count += memo[stu]
14 continue
15
16 if stu <= schools[0]:
17 diff = schools[0] - stu
18 elif stu > schools[-1]:
19 diff = stu - schools[-1]
20 else:
21 idx = b_l(schools, stu)
22 diff = min(stu - schools[idx - 1], schools[idx] - stu)
23
24 memo[stu] = diff
25 count += diff
26print(count)
另外一种方法是用前缀和。因为找到学生分数对应学校分数线区间的本质，就是先找出分数线比学生分数低的学校有多少，这个位置就是学生分数区间的下界。这样做也得对高分和低分学生特判。
1from collections import defaultdict
2
3m, n = map(int, input().strip().split())
4schools = list(map(int, input().strip().split()))
5students = tuple(map(int, input().strip().split()))
6schools.sort()
7
8cnt = [0] * (max(schools) + 1)
9for sch in schools:
10 cnt[sch] += 1
11prefsum = [0]
12for cc in cnt:
13 prefsum.append(prefsum[-1] + cc)
14
15memo = defaultdict(lambda: -1)
16count = 0
17for stu in students:
18 if memo[stu] != -1:
19 count += memo[stu]
20 continue
21
22 if stu >= len(prefsum):
23 diff = stu - schools[-1]
24 elif 0 < prefsum[stu] < m:
25 diff = min(stu - schools[prefsum[stu] - 1], schools[prefsum[stu]] - stu)
26 elif prefsum[stu] >= m:
27 diff = stu - schools[-1]
28 else:
29 diff = schools[0] - stu
30
31 memo[stu] = diff
32 count += diff
33
34print(count)
P1163 银行贷款
题目描述
当一个人从银行贷款后，在一段时间内他（她）将不得不每月偿还固定的分期付款。这个问题要求计算出贷款者向银行支付的利率。假设利率按月累计。
输入格式
三个用空格隔开的正整数。
第一个整数表示贷款的原值 $w_0$，第二个整数表示每月支付的分期付款金额 $w$，第三个整数表示分期付款还清贷款所需的总月数 $m$。
输出格式
一个实数，表示该贷款的月利率（用百分数表示），四舍五入精确到 $0.1%$。
数据保证答案不超过 $300.0%$。
输入输出样例 #1
输入 #1
11000 100 12
输出 #1
12.9
说明/提示
数据保证，$1 \leq w_0, w\leq 2^{31}-1$，$1 \leq m\leq 3000$。
题解
$w_0$，$w$，$m$ 和 $r$ 之间的关系是 $w_0 = w \cdot ( \frac{1 - (1 + r/100)^{-m}}{r/100} )$。使用浮点数二分查找解决。
1w0, w, m = map(int, input().strip().split())
2
3
4def interest(r):
5 return w * ((1 - (1 + r / 100) ** (-m)) / (r / 100))
6
7
8l, r = 0, 300
9while r - l >= 0.001:
10 mid = (l + r) / 2
11 if interest(mid) > w0:
12 l = mid
13 else:
14 r = mid
15
16print(f"{mid:.1f}")
P1873 [COCI 2011/2012 #5] EKO / 砍树
题目描述
伐木工人 Mirko 需要砍 $M$ 米长的木材。对 Mirko 来说这是很简单的工作，因为他有一个漂亮的新伐木机，可以如野火一般砍伐森林。不过，Mirko 只被允许砍伐一排树。
Mirko 的伐木机工作流程如下：Mirko 设置一个高度参数 $H$（米），伐木机升起一个巨大的锯片到高度 $H$，并锯掉所有树比 $H$ 高的部分（当然，树木不高于 $H$ 米的部分保持不变）。Mirko 就得到树木被锯下的部分。例如，如果一排树的高度分别为 $20,15,10$ 和 $17$，Mirko 把锯片升到 $15$ 米的高度，切割后树木剩下的高度将是 $15,15,10$ 和 $15$，而 Mirko 将从第 $1$ 棵树得到 $5$ 米，从第 $4$ 棵树得到 $2$ 米，共得到 $7$ 米木材。
Mirko 非常关注生态保护，所以他不会砍掉过多的木材。这也是他尽可能高地设定伐木机锯片的原因。请帮助 Mirko 找到伐木机锯片的最大的整数高度 $H$，使得他能得到的木材至少为 $M$ 米。换句话说，如果再升高 $1$ 米，他将得不到 $M$ 米木材。
输入格式
第 $1$ 行 $2$ 个整数 $N$ 和 $M$，$N$ 表示树木的数量，$M$ 表示需要的木材总长度。
第 $2$ 行 $N$ 个整数表示每棵树的高度。
输出格式
$1$ 个整数，表示锯片的最高高度。
输入输出样例 #1
输入 #1
14 7
220 15 10 17
输出 #1
115
输入输出样例 #2
输入 #2
15 20
24 42 40 26 46
输出 #2
136
说明/提示
对于 $100%$ 的测试数据，$1\le N\le10^6$，$1\le M\le2\times10^9$，树的高度 $\le 4\times 10^5$，所有树的高度总和 $>M$。
题解
这道题是一个特殊的二分查找，因为当锯片高度从 $l$ 到 $r$ 时，实际能锯下来的长度递减。因此在找这一边界元素的下标后，应当对下标减一才是正确的位置。因为序列中的元素需要访问时再求，因此没法用 bisect 模块或者是前缀和来求下标。
另外这道题用 Python 会爆内存，而且数据范围有 $2\times10^9$ 需要用 long long 存储。
1#define _CRT_SECURE_NO_WARNINGS
2#define LL long long
3
4#include <algorithm>
5#include <cstdio>
6
7using namespace std;
8
9int n, trees[1000005] = { 0 };
10LL m, len = 0ll;
11
12LL get(int x) {
13 len = 0;
14 for (int i = 0; i < n; i++) {
15 if (trees[i] > x) {
16 len += trees[i] - x;
17 }
18 }
19 return len;
20}
21
22int main() {
23 scanf("%d%d", &n, &m);
24 for (int i = 0; i < n; i++) {
25 scanf("%d", &trees[i]);
26 }
27 sort(trees, trees + n);
28
29 int l = 0, r = trees[n - 1];
30 while (l < r) {
31 int mid = (l + r) >> 1;
32 if (get(mid) >= m) {
33 l = mid + 1;
34 }
35 else {
36 r = mid;
37 }
38 }
39 printf("%d", l - 1);
40 return 0;
41}
P2440 木材加工
题目背景
要保护环境
题目描述
木材厂有 $n$ 根原木，现在想把这些木头切割成 $k$ 段长度均为 $l$ 的小段木头（木头有可能有剩余）。
当然，我们希望得到的小段木头越长越好，请求出 $l$ 的最大值。
木头长度的单位是 $\text{cm}$，原木的长度都是正整数，我们要求切割得到的小段木头的长度也是正整数。
例如有两根原木长度分别为 $11$ 和 $21$，要求切割成等长的 $6$ 段，很明显能切割出来的小段木头长度最长为 $5$。
输入格式
第一行是两个正整数 $n,k$，分别表示原木的数量，需要得到的小段的数量。
接下来 $n$ 行，每行一个正整数 $L_i$，表示一根原木的长度。
输出格式
仅一行，即 $l$ 的最大值。
如果连 $\text{1cm}$ 长的小段都切不出来，输出 0。
输入输出样例 #1
输入 #1
13 7
2232
3124
4456
输出 #1
1114
说明/提示
数据规模与约定
对于 $100%$ 的数据，有 $1\le n\le 10^5$，$1\le k\le 10^8$，$1\le L_i\le 10^8(i\in[1,n])$。
题解
和上一道题一样，这道题也是从 $l$ 到 $r$ 序列递减。
1import sys
2
3data = sys.stdin.read().strip().split("\n")
4n, k = map(int, data[0].strip().split())
5woods = list()
6for i in range(1, n + 1):
7 woods.append(int(data[i].strip()))
8
9
10def get(x):
11 count = 0
12 for w in woods:
13 count += w // x
14 return count
15
16
17l, r = 1, max(woods)
18while l < r:
19 mid = (l + r) >> 1
20 if get(mid) >= k:
21 l = mid + 1
22 else:
23 r = mid
24print(l - 1)
P2678 [NOIP 2015 提高组] 跳石头
题目背景
NOIP2015 Day2T1
题目描述
一年一度的“跳石头”比赛又要开始了！
这项比赛将在一条笔直的河道中进行，河道中分布着一些巨大岩石。组委会已经选择好了两块岩石作为比赛起点和终点。在起点和终点之间，有 $N$ 块岩石（不含起点和终点的岩石）。在比赛过程中，选手们将从起点出发，每一步跳向相邻的岩石，直至到达终点。
为了提高比赛难度，组委会计划移走一些岩石，使得选手们在比赛过程中的最短跳跃距离尽可能长。由于预算限制，组委会至多从起点和终点之间移走 $M$ 块岩石（不能移走起点和终点的岩石）。
输入格式
第一行包含三个整数 $L,N,M$，分别表示起点到终点的距离，起点和终点之间的岩石数，以及组委会至多移走的岩石数。保证 $L \geq 1$ 且 $N \geq M \geq 0$。
接下来 $N$ 行，每行一个整数，第 $i$ 行的整数 $D_i,( 0 < D_i < L)$， 表示第 $i$ 块岩石与起点的距离。这些岩石按与起点距离从小到大的顺序给出，且不会有两个岩石出现在同一个位置。
输出格式
一个整数，即最短跳跃距离的最大值。
输入输出样例 #1
输入 #1
125 5 2
22
311
414
517
621
输出 #1
14
说明/提示
输入输出样例 1 说明
将与起点距离为 $2$ 和 $14$ 的两个岩石移走后，最短的跳跃距离为 $4$（从与起点距离 $17$ 的岩石跳到距离 $21$ 的岩石，或者从距离 $21$ 的岩石跳到终点）。
数据规模与约定
对于 $20%$的数据，$0 \le M \le N \le 10$。 对于 $50%$ 的数据，$0 \le M \le N \le 100$。 对于 $100%$ 的数据，$0 \le M \le N \le 50000,1 \le L \le 10^9$。
题解
首先求出数列这些石头两两之间的距离并且存储到一个长度为 $n+1$ 的列表中，此时题目就转换成了一个区间合并问题：做 $m$ 次合并相邻两数的操作，求出这些操作结束后列表最小值最大可能的值。具体做法是用二分查找计算出一个可能的最小值 min_val，然后对原列表做合并操作：累加列表中一段连续的值直到他们的和大于等于 min_val，将这个和追加到新列表中。如果最后这个新列表的长度大于等于 $n-m$ 就是合法的，最理想也是最后要求解的情况是这个新列表的长度刚好为 $n-m$。根据这个特性也不难看出，这道题的序列还是从 $l$ 到 $r$ 递减。
1import sys
2
3data = sys.stdin.read().strip().split("\n")
4l, n, m = map(int, data[0].strip().split())
5if n == m == 0:
6 print(l)
7 exit()
8dist = [int(data[1])]
9for i in range(1, n):
10 dist.append(int(data[i + 1]) - int(data[i]))
11dist.append(l - int(data[-1]))
12
13
14def get(x):
15 removed = list()
16 seg = 0
17 for i in range(n):
18 seg += dist[i]
19 if seg >= x:
20 removed.append(seg)
21 seg = 0
22 return len(removed)
23
24
25lo, hi = min(dist), max(dist)
26while lo < hi:
27 mid = (lo + hi) >> 1
28 if get(mid) >= n - m:
29 lo = mid + 1
30 else:
31 hi = mid
32print(lo - 1)
P3853 [TJOI2007] 路标设置
题目背景
B 市和 T 市之间有一条长长的高速公路，这条公路的某些地方设有路标，但是大家都感觉路标设得太少了，相邻两个路标之间往往隔着相当长的一段距离。为了便于研究这个问题，我们把公路上相邻路标的最大距离定义为该公路的“空旷指数”。
题目描述
现在政府决定在公路上增设一些路标，使得公路的“空旷指数”最小。他们请求你设计一个程序计算能达到的最小值是多少。请注意，公路的起点和终点保证已设有路标，公路的长度为整数，并且原有路标和新设路标都必须距起点整数个单位距离。
输入格式
第 $1$ 行包括三个数 $L,N,K$，分别表示公路的长度，原有路标的数量，以及最多可增设的路标数量。
第 $2$ 行包括递增排列的 $N$ 个整数，分别表示原有的 $N$ 个路标的位置。路标的位置用距起点的距离表示，且一定位于区间 $[0,L]$ 内。
输出格式
输出 $1$ 行，包含一个整数，表示增设路标后能达到的最小“空旷指数”值。
输入输出样例 #1
输入 #1
1101 2 1
20 101
输出 #1
151
说明/提示
公路原来只在起点和终点处有两个路标，现在允许新增一个路标，应该把新路标设在距起点 $50$ 或 $51$ 个单位距离处，这样能达到最小的空旷指数 $51$。
$50%$ 的数据中，$2 \leq N \leq 100$，$0 \leq K \leq 100$。
$100%$ 的数据中，$2 \leq N \leq 100000$, $0 \leq K \leq100000$。
$100%$ 的数据中，$0 < L \leq 10000000$。
题解
和上一道题相反，这道题是要分割区间求出最小的最大值，但是思路和上一题类似。
1l, n, k = map(int, input().strip().split())
2signs = tuple(map(int, input().strip().split()))
3dist = list()
4for i in range(n - 1):
5 dist.append(signs[i + 1] - signs[i])
6
7
8def get(x):
9 seg = 0
10 settled = list()
11 for i in range(n - 1):
12 seg = dist[i]
13 while seg > x:
14 settled.append(x)
15 seg -= x
16 settled.append(seg)
17 return len(settled)
18
19
20lo, hi = 1, max(dist)
21while lo < hi:
22 mid = (lo + hi) >> 1
23 if get(mid) >= n + k:
24 lo = mid + 1
25 else:
26 hi = mid
27print(lo)
虽然这道题的序列还是从 $l$ 到 $r$ 递减，但是最后求出来的 lo 并不需要减一。
P1182 数列分段 Section II
题目描述
对于给定的一个长度为 $N$ 的正整数数列 $A_{1\sim N}$，现要将其分成 $M$（$M\leq N$）段，并要求每段连续，且每段和的最大值最小。
关于最大值最小：
例如一数列 $4\ 2\ 4\ 5\ 1$ 要分成 $3$ 段。
将其如下分段：
$$[4\ 2][4\ 5][1]$$
第一段和为 $6$，第 $2$ 段和为 $9$，第 $3$ 段和为 $1$，和最大值为 $9$。
将其如下分段：
$$[4][2\ 4][5\ 1]$$
第一段和为 $4$，第 $2$ 段和为 $6$，第 $3$ 段和为 $6$，和最大值为 $6$。
并且无论如何分段，最大值不会小于 $6$。
所以可以得到要将数列 $4\ 2\ 4\ 5\ 1$ 要分成 $3$ 段，每段和的最大值最小为 $6$。
输入格式
第 $1$ 行包含两个正整数 $N,M$。
第 $2$ 行包含 $N$ 个空格隔开的非负整数 $A_i$，含义如题目所述。
输出格式
一个正整数，即每段和最大值最小为多少。
输入输出样例 #1
输入 #1
15 3
24 2 4 5 1
输出 #1
16
说明/提示
对于 $20%$ 的数据，$N\leq 10$。
对于 $40%$ 的数据，$N\leq 1000$。
对于 $100%$ 的数据，$1\leq N\leq 10^5$，$M\leq N$，$A_i < 10^8$， 答案不超过 $10^9$。
题解
这道题是要求合并区间后最大值最小为多少，合并规则为：从左到右遍历列表，累计当前区间的和。如果当前区间的和超过 $x$，则需要进行一次合并操作，将当前元素与下一个元素合并，并重置当前区间的和。
1n, m = map(int, input().strip().split())
2nums = tuple(map(int, input().strip().split()))
3
4
5def get(x):
6 curr = 0
7 count = 0
8 for num in nums:
9 curr += num
10 if curr > x:
11 count += 1
12 curr = num
13 return count
14
15
16l, r = max(nums), sum(nums)
17while l < r:
18 mid = (l + r) >> 1
19 if get(mid) > m - 1:
20 l = mid + 1
21 else:
22 r = mid
23print(l)
P3743 小鸟的设备
题目背景
小鸟有 $n$ 个可同时使用的设备。
题目描述
第 $i$ 个设备每秒消耗 $a_i$ 个单位能量。能量的使用是连续的，也就是说能量不是某时刻突然消耗的，而是匀速消耗。也就是说，对于任意实数，在 $k$ 秒内消耗的能量均为 $k\times a_i$ 单位。在开始的时候第 $i$ 个设备里存储着 $b_i$ 个单位能量。
同时小鸟又有一个可以给任意一个设备充电的充电宝，每秒可以给接通的设备充能 $p$ 个单位，充能也是连续的，不再赘述。你可以在任意时间给任意一个设备充能，从一个设备切换到另一个设备的时间忽略不计。
小鸟想把这些设备一起使用，直到其中有设备能量降为 $0$。所以小鸟想知道，在充电器的作用下，她最多能将这些设备一起使用多久。
输入格式
第一行给出两个整数 $n,p$。
接下来 $n$ 行，每行表示一个设备，给出两个整数，分别是这个设备的 $a_i$ 和 $b_i$。
输出格式
如果小鸟可以无限使用这些设备，输出 $-1$。
否则输出小鸟在其中一个设备能量降为 $0$ 之前最多能使用多久。
设你的答案为 $a$，标准答案为 $b$，只有当 $a,b$ 满足 $\dfrac{|a-b|}{\max(1,b)} \leq 10^{-4}$ 的时候，你能得到本测试点的满分。
输入输出样例 #1
输入 #1
12 1
22 2
32 1000
输出 #1
12.0000000000
输入输出样例 #2
输入 #2
11 100
21 1
输出 #2
1-1
输入输出样例 #3
输入 #3
13 5
24 3
35 2
46 1
输出 #3
10.5000000000
说明/提示
对于 $100%$ 的数据，$1\leq n\leq 100000$，$1\leq p\leq 100000$，$1\leq a_i,b_i\leq100000$。
题解
关键在于 get 函数的写法。在验证的时间内，如果某台设备的消耗大于等于存量，则将其添加到总消耗量中，用这个总消耗量与验证的时间内充电器输出的能量做比较。剩下的就是用浮点数二分查找时间。
1import sys
2
3data = sys.stdin.read().strip().split("\n")
4n, p = map(int, data[0].strip().split())
5a, b = list(), list()
6for i in range(1, n + 1):
7 ai, bi = map(int, data[i].strip().split())
8 a.append(ai)
9 b.append(bi)
10
11if sum(a) <= p:
12 print(-1)
13 exit()
14
15
16def get(k):
17 consumption = 0
18 for i in range(n):
19 if b[i] - k * a[i] <= 0:
20 consumption += k * a[i] - b[i]
21 return consumption > p * k
22
23
24l, r = 0, 1e10
25while r - l > 10e-6:
26 mid = (l + r) / 2
27 if get(mid):
28 r = mid
29 else:
30 l = mid
31print(l)