二分查找与前缀和练习

2025-02-09 · 7 分钟阅读 · 算法二分查找前缀和 ·

复制链接:

文章目录

题目来自 AcWing

789. 数的范围 | 原题链接

这道题做法很多。

使用双指针将每一段的信息存储到字典中：

 1n, q = map(int, input().strip().split(" "))
 2nums = tuple(map(int, input().strip().split(" ")))
 3d = dict()
 4l = len(nums)
 5
 6front = 0
 7rear = 0
 8while front < l:
 9    if nums[front] != nums[rear]:
10        d[nums[rear]] = (rear, front - 1)
11        rear = front
12    front += 1
13
14d[nums[rear]] = (rear, front - 1)
15
16result = list()
17for _ in range(q):
18    k = int(input().strip())
19    a, b = d.get(k, (-1, -1))
20    print(a, b)

二分查找段首和段尾：

 1n, q = map(int, input().split(" "))
 2nums = tuple(map(int, input().split(" ")))
 3
 4for _ in range(q):
 5    k = int(input())
 6    L = 0
 7    R = n - 1
 8    while L != R:
 9        mid = (L + R) // 2
10        if nums[mid] < k:
11            L = mid + 1
12        else:
13            R = mid
14    if nums[R] != k:
15        print("-1 -1")
16        continue
17    a = R
18
19    L = 0
20    R = n - 1
21    while L != R:
22        mid = (L + R) // 2 + 1
23        if nums[mid] <= k:
24            L = mid
25        else:
26            R = mid - 1
27    b = L
28    print(a, b)

注意当查找段首和段尾时，左右指针的变换规则不同。

790. 数的三次方根 | 原题链接

暴力解法：

1n = float(input())
2if n >= 0:
3    print(f"{n ** (1 / 3):.6f}")
4else:
5    k = (-n) ** (1 / 3)
6    print(f"{-k:.6f}")

当 n 是负数时，开三次方跟会开出来复数，所以要特判。

二分查找：

 1n = float(input())
 2
 3L = -10000.0
 4R = 10000.0
 5
 6while R - L >= 1e-7:
 7    mid = (L + R) / 2
 8    k = mid ** 3
 9    if k > n:
10        R = mid
11    elif k < n:
12        L = mid
13    else:
14        break
15
16print(f"{mid - 1e-7:.6f}")

二分查找的速度比硬算快，但是最后要减去 1e-7 才能 AC，原理不清楚，可能与 Python 保留精度的机制有关。

另外，无论是 f-string，format 函数还是 round 函数，其保留精度都是通过四舍五入完成的，f-string 与 format 函数会保留末位 0 而 round 函数不会。

795. 前缀和 | 原题链接

利用前缀和解决即可

 1n, q = map(int, input().split(" "))
 2nums = (0,) + tuple(map(int, input().split(" ")))
 3
 4pref = [0]
 5for i in range(1, n + 1):
 6    pref.append(pref[i - 1] + nums[i])
 7
 8for _ in range(q):
 9    l, r = map(int, input().split(" "))
10    print(pref[r] - pref[l - 1])

796. 子矩阵的和 | 原题链接

前缀和二维版。利用容斥原理，使用已知的前缀和来计算当前前缀和，即 pref[i][j] = pref[i][j - 1] + matrix[i][j] + pref[i - 1][j] - pref[i - 1][j - 1]。

 1n, m, q = map(int, input().split())
 2matrix = [[0] * (m + 1)]
 3for _ in range(n):
 4    row = [0] + list(map(int, input().split()))
 5    matrix.append(row)
 6
 7pref = [[0 for _ in range(m + 1)] for _ in range(n + 1)]
 8for i in range(1, n + 1):
 9    for j in range(1, m + 1):
10        pref[i][j] = pref[i][j - 1] + matrix[i][j] + pref[i - 1][j] - pref[i - 1][j - 1]
11
12for _ in range(q):
13    x1, y1, x2, y2 = map(int, input().split())
14    print(pref[x2][y2] - pref[x1 - 1][y2] - pref[x2][y1 - 1] + pref[x1 - 1][y1 - 1])

730. 机器人跳跃问题 | 原题链接

这道题可以使用二分查找解决。当机器人的初始能量与最高塔高相同时，机器人保证能通过。因此在这个范围内查找机器人能够通过与不能通过的分界点。使用二分查找可以将时间复杂度从 O(n) 降低至 O(logn)。

 1n = int(input())
 2nums = tuple(map(int, input().split(" ")))
 3
 4
 5def simulate(nums, n, e):
 6    for i in range(n):
 7        if e < 0:
 8            return False
 9
10        if e < nums[i]:
11            e -= nums[i] - e
12        else:
13            e += e - nums[i]
14    if e >= 0:
15        return True
16    else:
17        return False
18
19
20L = 0
21R = max(nums)
22result = R
23
24while L < R:
25    mid = (L + R) // 2
26    if simulate(nums, n, mid):
27        result = mid
28        R = mid
29    else:
30        L = mid + 1
31
32print(result)

1221. 四平方和 | 原题链接

逐层遍历四个数肯定是要超时的，因此需要想其他办法解决。观察等式 $n=a^2+b^2+c^2+d^2$，可以将四个自变量两两分组，得到 $n-(c^2+d^2)=a^2+b^2$。只需要从 0 开始遍历 c 与 d，随后将所有可能的 $c^2+d^2$ 的值存储起来，然后在存储的值中查找是否有满足条件的平方和即可。这个思路相当于在遍历 c 与 d 时，同时遍历了 a 与 b 可能的结果，因此将时间复杂度从 O(n⁴) 降低到 O(n²)。

 1n = int(input())
 2sqrtn = int(n**0.5) + 1
 3
 4record = dict()
 5
 6for c in range(0, sqrtn):
 7    for d in range(c, sqrtn):
 8        sum_cd = c**2 + d**2
 9        if sum_cd > n:
10            break
11        if not record.get(sum_cd, False):
12            record[sum_cd] = (c, d)
13
14for sum_cd in record.keys():
15    if record.get(n - sum_cd, False):
16        a, b = record[n - sum_cd]
17        c, d = record[sum_cd]
18        print(*sorted((a, b, c, d)))
19        exit()

至于为什么 record 中只存储使 c d 满足 $c^2+d^2=m,m\leq n$ 的第一组数，是因为第一次出现这样的 c d 时，其联合主键一定是字典序最小的。另外根据 Python3 中字典键顺序为插入顺序的特性，record 中键的顺序又是其值（即 a b 或 c d 组成的有序数对）作为联合主键的字典序，因此在最后遍历字典时，能够保证 $c\geq a,d\geq b$。

1227. 分巧克力 | 原题链接

还是使用二分查找来解决，这道题属于查找左侧段的右边界。这道题的坑在于，并不是每一块巧克力都会被切开分出去，所以 R 的初始值应该是所有边长的最大值而非最小值。

 1n, k = map(int, input().split(" "))
 2chocolates = list()
 3R = float("-inf")
 4for _ in range(n):
 5    choco = tuple(map(int, input().split(" ")))
 6    chocolates.append(choco)
 7    R = max(R, max(choco))
 8
 9
10def check(chocolates, d, k):
11    count = 0
12    for x, y in chocolates:
13        count += (x // d) * (y // d)
14    return count >= k
15
16
17L = 1
18d = 1
19while L != R:
20    mid = (L + R) // 2 + 1
21    if check(chocolates, mid, k):
22        d = mid
23        L = mid
24    else:
25        R = mid - 1
26
27print(d)

99. 激光炸弹 | 原题链接

二维前缀和。注意一枚炸弹的半径可能能够将全部目标摧毁，所以要依据 x y r 的关系分情况讨论。

 1#define _CRT_SECURE_NO_WARNINGS
 2
 3#include <algorithm>
 4#include <cstdio>
 5
 6using namespace std;
 7
 8int targets[5005][5005] = { 0 };
 9
10int main() {
11    int n, r;
12    int xi, yi, wi;
13    int max_x = 0, max_y = 0;
14    scanf("%d%d", &n, &r);
15    for (int i = 1; i <= n; i++) {
16        scanf("%d%d%d", &xi, &yi, &wi);
17        xi++;
18        yi++;
19        max_x = max(max_x, xi);
20        max_y = max(max_y, yi);
21        targets[xi][yi] += wi;
22    }
23
24    int max_w = 0;
25    for (int x = 1; x <= max_x; x++) {
26        for (int y = 1; y <= max_y; y++) {
27            targets[x][y] = targets[x - 1][y] + targets[x][y - 1] - targets[x - 1][y - 1] + targets[x][y];
28            if (x >= r && y >= r) {
29                max_w = max(max_w, targets[x][y] - targets[x - r][y] - targets[x][y - r] + targets[x - r][y - r]);
30            }
31            else if (x >= r && y < r) {
32                max_w = max(max_w, targets[x][y] - targets[x - r][y]);
33            }
34            else if (x < r && y >= r) {
35                max_w = max(max_w, targets[x][y] - targets[x][y - r]);
36            }
37            else {
38                max_w = max(max_w, targets[x][y]);
39            }
40        }
41    }
42
43    printf("%d\n", max_w);
44    return 0;
45}

直接在原矩阵中生成前缀和矩阵，否则会 MLE。Python 无论如何也过不了，而且问题似乎出在平台。

好吧，Python 和 Python3 是两种不同的测试环境……是我的问题。

 1targets = [[0 for _ in range(5005)] for _ in range(5005)]
 2n, r = map(int, input().split(" "))
 3
 4max_x, max_y = 0, 0
 5for _ in range(n):
 6    x, y, w = map(int, input().split(" "))
 7    x += 1
 8    y += 1
 9    max_x = max(max_x, x)
10    max_y = max(max_y, y)
11    targets[x][y] += w
12
13max_w = 0
14for x in range(1, max_x + 1):
15    for y in range(1, max_y + 1):
16        targets[x][y] += targets[x - 1][y] + targets[x][y - 1] - targets[x - 1][y - 1]
17        if x >= r and y >= r:
18            max_w = max(
19                max_w,
20                targets[x][y]
21                - targets[x - r][y]
22                - targets[x][y - r]
23                + targets[x - r][y - r],
24            )
25        elif x >= r and y < r:
26            max_w = max(max_w, targets[x][y] - targets[x - r][y])
27        elif x < r and y >= r:
28            max_w = max(max_w, targets[x][y] - targets[x][y - r])
29        else:
30            max_w = max(max_w, targets[x][y])
31
32print(max_w)

1230. K倍区间 | 原题链接

依然使用前缀和解决。题目要求在前缀和数组中找出所有差能够整除 k 的数对的数量，如果使用两层循环，则一定会超时，因此使用数学方法优化。假设存在两数 $i,j,(i<j)$ 使得 $(j-i)\space mod\space k=0$，变换后得到 $i\equiv j\space (mod\space k)$。因此可以创建一个字典用于存储同余类，然后遍历字典得到所有组合。

 1n, k = map(int, input().split(" "))
 2pref = [0]
 3record = {0: [0]}
 4for _ in range(n):
 5    num = int(input())
 6    pref.append(num + pref[-1])
 7    r = record.get(pref[-1] % k, list())
 8    r.append(pref[-1])
 9    record[pref[-1] % k] = r
10
11count = 0
12for k in record.keys():
13    if len(record[k]) >= 2:
14        count += len(record[k]) * (len(record[k]) - 1) // 2
15
16print(count)