小鲸鱼的梦境
0%

『洛谷』二分

发表于 更新于 分类于 ， Valine：
本文字数： 16k 阅读时长 ≈ 14 分钟

基础算法-二分

P1024 [NOIP2001 提高组] 一元三次方程求解

题目描述

有形如：\(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 \lt x_2\)，\(f(x_1) \times f(x_2) \lt 0\)，则在 \((x_1, x_2)\) 之间一定有一个根。

输入格式

一行，\(4\) 个实数 \(a, b, c, d\)。

输出格式

一行，\(3\) 个实根，从小到大输出，并精确到小数点后 \(2\) 位。

输入输出样例

输入: #1

1
1 -5 -4 20

输出: #1

1
-2.00 2.00 5.00

说明&提示

无

解题思路

枚举+二分即可

因为答案范围200，精度要求 两位，所以甚至可以每次 +0.01 进行枚举

稍微好点的办法就是枚举大小为 1 的区间然后区间内用二分查找，注意精度问题即可

更进阶方法可以是牛顿迭代法、割线法、盛金公式、卡尔丹公式（后两个是数学方法直接给出三个根的公式）

解答代码

枚举+二分

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#include <cstdio>
using namespace std;

double a, b, c, d;
double ans[3];

inline double fx(double x) {
    return ((a * x + b) * x + c) * x + d;
}

inline int sign(double x) {
    if (x > 0.01) return 1;
    if (x < -0.01) return -1;
    return 0;
}

// 查找区间内一个零点
inline double find(double left, double right) {
    int l = sign(fx(left)), r = sign(fx(right));
    while (right - left >= 0.01) {
        double mid = (left + right) / 2;
        int m = sign(fx(mid));
        if (l + m == 0)
            right = mid;
        else if (r + m == 0)
            left = mid;
        else
            return mid;
    }
    return left;
}

int main() {
    scanf("%lf%lf%lf%lf", &a, &b, &c, &d);
    // 在 [-100,100] 枚举长度为 1 的区间
    int aa = sign(fx(-101)), bb = sign(fx(-100)), i = 0;
    for (double l = -101; l < 101; l += 1) {
        if (aa == 0) {
            ans[i++] = l;
            if (i == 3) break;
        }
        if (aa + bb == 0 && aa - bb != 0) {
            ans[i++] = find(l, l + 1);
            if (i == 3) break;
        }
        aa = bb;
        bb = sign(fx(l + 2));
    }
    for (int i = 0; i < 3; ++i) {
        printf("%.2f ", ans[i]);
    }
    return 0;
}

P2678 [NOIP2015 提高组] 跳石头

题目描述

一年一度的“跳石头”比赛又要开始了!

这项比赛将在一条笔直的河道中进行，河道中分布着一些巨大岩石。组委会已经选择好了两块岩石作为比赛起点和终点。在起点和终点之间，有 \(N\) 块岩石（不含起点和终点的岩石）。在比赛过程中，选手们将从起点出发，每一步跳向相邻的岩石，直至到达终点。

为了提高比赛难度，组委会计划移走一些岩石，使得选手们在比赛过程中的最短跳跃距离尽可能长。由于预算限制，组委会至多从起点和终点之间移走 \(M\) 块岩石（不能移走起点和终点的岩石）。

输入格式

第一行包含三个整数 \(L,N,M\)，分别表示起点到终点的距离，起点和终点之间的岩石数，以及组委会至多移走的岩石数。保证 \(L \geq 1\) 且 \(N \geq M \geq 0\)。

接下来 \(N\) 行，每行一个整数，第 \(i\) 行的整数 \(D_i( 0 \lt D_i \lt L)\)， 表示第 \(i\) 块岩石与起点的距离。这些岩石按与起点距离从小到大的顺序给出，且不会有两个岩石出现在同一个位置。

输出格式

一个整数，即最短跳跃距离的最大值。

输入输出样例

输入: #1

1
2
3
4
5
6
25 5 2 
2
11
14
17 
21

输出: #1

1
4

说明&提示

输入输出样例 1 说明：将与起点距离为 \(2\)和 \(14\) 的两个岩石移走后,最短的跳跃距离为 \(4\)(从与起点距离 \(17\) 的岩石跳到距离 \(21\) 的岩石,或者从距离 \(21\) 的岩石跳到终点)。

另：对于 \(20\%\)的数据,\(0 ≤ M ≤ N ≤ 10\)。

对于\(50\%\)的数据,\(0 ≤ M ≤ N ≤ 100\)。

对于 \(100\%\)的数据,\(0 ≤ M ≤ N ≤ 50,000,1 ≤ L ≤ 1,000,000,000\)。

解题思路

第一想法当然是贪心，每次移走距离靠得最近的石头，就能保证最后最短跳跃距离最大，可以用堆来维护石头间距，感觉应该是可行的但有诸多小问题

第二种方法是用猜数字的方法来求解，若知道最短跳跃距离，我们很容易就能求出需要移除的石头数量(因为要使跳跃距离最短，那么毫无疑问是不跨石头跳跃，即每次都跳到相邻石头，若两块石头的距离小于最短跳跃距离，那么就要移除掉一块石头，否则就存在了比最短跳跃距离还要短的跳跃距离据此可以计算出需要移除的石头数量)，而最短跳跃距离越大，可移除的石头数量是单调非减的，所以满足二段性，可以使用二分法直接估计最短跳跃距离然后求解。

  • 时间复杂度: \(O(N \log L)\)
  • 空间复杂度: \(O(N)\)

解答代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
def check(st, jump):
    """ 给出跳跃距离，返回移除石头数量 """
    pre, cnt = 0, 0
    for a in st:
        if a - pre < jump:
            cnt += 1
        else:
            pre = a
    return cnt
        

def main():
    dist, n, m = map(int, input().split())
    st = [int(input()) for _ in range(n)]
    st.append(dist)
    left, right = 0, int(2e9)
    while left < right:
        mid = (left + right + 1) >> 1
        if check(st, mid) <= m:
            left = mid
        else:
            right = mid - 1
    print(left)
main()
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

#include <bits/stdc++.h>
using namespace std;

const int M = 50005;
int arr[M];

int check(int m, int jump) {
    int pre = 0, cnt = 0;
    for (int i = 0; i < m; ++i) {
        if (arr[i] - pre < jump)
            ++cnt;
        else
            pre = arr[i];
    }
    return cnt;
}

int main() {
    int dist, n, m;
    scanf("%d%d%d", &dist, &n, &m);
    for (int i = 0; i < n; ++i) {
        scanf("%d", &arr[i]);
    }
    arr[n] = dist;
    int left = 0, right = 2000000000;
    while (left < right) {
        int mid = left + ((right - left + 1) >> 1);
        if (check(n + 1, mid) <= m)
            left = mid;
        else
            right = mid - 1;
    }
    printf("%d", left);
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
import java.util.*;

class Main {

    public static void main(String[] args) {
        Main s = new Main();
        s.jump_stone();
    }

    public void jump_stone() {

        Scanner sc = new Scanner(System.in);
        int dist = sc.nextInt(), n = sc.nextInt(), m = sc.nextInt();
        int[] st = new int[n + 1];
        for (int i = 0; i < n; ++i) {
            st[i] = sc.nextInt();
        }
        st[n] = dist;
        int left = 0,
                right = 2000000000;
        while (left < right) {
            int mid = left + (right - left + 1 >> 1);
            if (check(st, mid) <= m)
                left = mid;
            else
                right = mid - 1;
        }
        System.out.println(left);

        sc.close();
    }

    public int check(int[] st, int jump) {
        int pre = 0, cnt = 0;
        for (int a : st) {
            if (a - pre < jump)
                ++cnt;
            else
                pre = a;
        }
        return cnt;
    }
}

P1902 刺杀大使

题目描述

某组织正在策划一起对某大使的刺杀行动。他们来到了使馆，准备完成此次刺杀，要进入使馆首先必须通过使馆前的防御迷阵。

迷阵由 \(n\times m\) 个相同的小房间组成，每个房间与相邻四个房间之间有门可通行。在第 \(n\) 行的 \(m\) 个房间里有 \(m\) 个机关，这些机关必须全部打开才可以进入大使馆。而第 \(1\) 行的 \(m\) 个房间有 \(m\) 扇向外打开的门，是迷阵的入口。除了第 \(1\) 行和第 \(n\) 行的房间外，每个房间都被使馆的安保人员安装了激光杀伤装置，将会对进入房间的人造成一定的伤害。第 \(i\) 行第 \(j\) 列 造成的伤害值为 \(p_{i,j}\)（第 \(1\) 行和第 \(n\) 行的 \(p\) 值全部为 \(0\)）。

现在某组织打算以最小伤害代价进入迷阵，打开全部机关，显然，他们可以选 择任意多的人从任意的门进入，但必须到达第 \(n\) 行的每个房间。一个士兵受到的伤害值为他到达某个机关的路径上所有房间的伤害值中的最大值，整个部队受到的伤害值为所有士兵的伤害值中的最大值。现在，这个恐怖组织掌握了迷阵的情况，他们需要提前知道怎么安排士兵的行进路线可以使得整个部队的伤害值最小。

输入格式

第一行有两个整数 \(n,m\)，表示迷阵的大小。

接下来 \(n\) 行，每行 \(m\) 个数，第 \(i\) 行第 \(j\) 列的数表示 \(p_{i,j}\)。

输出格式

输出一个数，表示最小伤害代价。

样例 #1

样例输入 #1

1
2
3
4
5
4 2
0 0 
3 5 
2 4 
0 0

样例输出 #1

1
3

提示

  • \(50\%\) 的数据，\(n,m \leq 100\)；
  • \(100\%\) 的数据，\(n,m \leq 1000\)，\(p_{i,j} \leq 1000\)。

解题思路

最开始的想法其实是动态规划，但动态规划不适合这种四个方向都可以前进的，更适合的方法其实是 BFS 或 DFS，但直接对路线进行搜索遍历代价太大了，而且最小化路线上的最大伤害值这个非常麻烦，但是反过来，如果要确定能否以某个代价通过迷宫却是比较简单的事情，因此考虑使用二分猜答案的方法进行求解。

  • 时间复杂度: \(O(n^2 \log n)\)

解答代码

Python 栈会溢出，所以必须调整递归栈大小，但还是没法通过全部用例, 但同样的方法 C++ 可以通过

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
import sys

sys.setrecursionlimit(1000000)

dir = ((1, 0), (0, 1), (0, -1), (-1, 0))

def xy2int(x, y):
    return x * 1007 + y

def dfs(mat, cur: int, vis: set, i: int, j: int):
    if mat[i][j] > cur:
        return False
    n, m = len(mat), len(mat[0])
    if i == n - 1:
        return True
    vis.add(xy2int(i, j))
    for dx, dy in dir:
        x, y = i + dx, j + dy
        if x < 0 or x >= n or y < 0 or y >= m:
            continue
        key = xy2int(x, y)
        if key not in vis and dfs(mat, cur, vis, x, y):
            return True
    return False

def check(mat, cur):
    vis = set()
    return dfs(mat, cur, vis, 0, 0)


def main():
    n, m = map(int, input().split())
    mat = [list(map(int, input().split())) for _ in range(n)]

    left, right = min(min(a) for a in mat), max(max(a) for a in mat)
    while left < right:
        mid = (left + right) >> 1
        if check(mat, mid):
            right = mid
        else:
            left = mid + 1
    print(left)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#include <bits/stdc++.h>
using namespace std;

const int N = 1007;
int mat[N][N], vis[N * N];
int n, m;
int dir_x[]{1, 0, 0, -1}, dir_y[]{0, 1, -1, 0};

int xy2int(int x, int y) {
    return x * N + y;
}

bool dfs(int i, int j, int cur) {
    if (mat[i][j] > cur) return false;
    if (i == n - 1) return true;
    vis[xy2int(i, j)] = 1;
    for (int k = 0; k < 4; ++k) {
        int dx = dir_x[k], dy = dir_y[k];
        int x = i + dx, y = j + dy;
        if (x < 0 || x >= n || y < 0 || y >= m || mat[x][y] > cur || vis[xy2int(x, y)] == 1)
            continue;
        if (dfs(x, y, cur)) return true;
    }
    return false;
}

bool check(int cur) {
    memset(vis, 0, sizeof(vis));
    return dfs(0, 0, cur);
}

int main() {
    int left = 0, right = N * N, mid;
    scanf("%d%d", &n, &m);
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            scanf("%d", &mat[i][j]);
            right = right < mat[i][j] ? mat[i][j] : right;
        }
    }
    while (left < right) {
        mid = (left + right) >> 1;
        if (check(mid))
            right = mid;
        else
            left = mid + 1;
    }
    printf("%d", left);
    return 0;
}

P1314 [NOIP2011 提高组] 聪明的质监员

题目描述

小T 是一名质量监督员，最近负责检验一批矿产的质量。这批矿产共有 \(n\) 个矿石，从 \(1\) 到 \(n\) 逐一编号，每个矿石都有自己的重量 \(w_i\) 以及价值 \(v_i\) 。检验矿产的流程是：

1 、给定$ m$ 个区间 \([l_i,r_i]\)；

2 、选出一个参数 \(W\)；

3 、对于一个区间 \([l_i,r_i]\)，计算矿石在这个区间上的检验值 \(y_i\)：

\[ y_i=\sum\limits_{j=l_i}^{r_i}[w_j \ge W] \times \sum\limits_{j=l_i}^{r_i}[w_j \ge W]v_j \]

其中 \(j\) 为矿石编号。

这批矿产的检验结果 \(y\) 为各个区间的检验值之和。即：\(\sum\limits_{i=1}^m y_i\)

若这批矿产的检验结果与所给标准值 \(s\) 相差太多，就需要再去检验另一批矿产。小T 不想费时间去检验另一批矿产，所以他想通过调整参数 \(W\) 的值，让检验结果尽可能的靠近标准值 \(s\)，即使得 \(|s-y|\) 最小。请你帮忙求出这个最小值。

输入格式

第一行包含三个整数 \(n,m,s\)，分别表示矿石的个数、区间的个数和标准值。

接下来的 \(n\) 行，每行两个整数，中间用空格隔开，第 \(i+1\) 行表示 \(i\) 号矿石的重量 \(w_i\) 和价值 \(v_i\)。

接下来的 \(m\) 行，表示区间，每行两个整数，中间用空格隔开，第 \(i+n+1\) 行表示区间 \([l_i,r_i]\) 的两个端点 \(l_i\) 和 \(r_i\)。注意：不同区间可能重合或相互重叠。

输出格式

一个整数，表示所求的最小值。

样例 #1

样例输入 #1

1
2
3
4
5
6
7
8
9
5 3 15 
1 5 
2 5 
3 5 
4 5 
5 5 
1 5 
2 4 
3 3

样例输出 #1

1
10

提示

【输入输出样例说明】

当 \(W\) 选 \(4\) 的时候，三个区间上检验值分别为 \(20,5 ,0\) ，这批矿产的检验结果为 \(25\)，此时与标准值 \(S\) 相差最小为 \(10\)。

【数据范围】

对于 $10% $ 的数据，有 \(1 ≤n ,m≤10\)；

对于 $30% $的数据，有 \(1 ≤n ,m≤500\) ；

对于 $50% $ 的数据，有 $ 1 ≤n ,m≤5,000$；

对于 \(70\%\) 的数据，有 \(1 ≤n ,m≤10,000\) ；

对于 \(100\%\) 的数据，有 $ 1 ≤n ,m≤200,000$，\(0 < w_i,v_i≤10^6\)，\(0 < s≤10^{12}\)，\(1 ≤l_i ≤r_i ≤n\) 。

解题思路

其实计算 \(y_i\) 的公式有点迷惑，但结合用例可以看出，区间其实是矿石的编号，而计算方法是满足矿石质量大于 \(W\) 的数量以及对应的质量和的乘积，不难发现最终的校验结果和 \(W\) 的大小时成反比的，简单看就是 \(W\) 越大，满足条件 \(w_i > W\) 的数量越少，质量和也越少，\(y_i\) 也越小，所以最终结果也最小。

结合题目看想直接求解 \(W\) 是困难的，但如果知道 \(W\) 计算校验结果是容易的，所以使用二分的方法“猜答案”。

因为二分的过程需要多次查询大于某个 \(W\) 的矿石的数量和质量，所以不难想到可以通过前缀和优化查询过程。

因为要计算与 \(s\) 的最小差值，有两个办法，时间复杂度是一致的：

  1. 直接用差值，此时 \(W\) 的取值是一个 \(V\) 形的谷函数，这种情况其实用三分更合适一些
  2. 查询两个值，比 \(s\) 大的最小值和比 \(s\) 小的最大值

最后时间复杂度为 \(O((n + m)\log C + n \log n)\), 其中 \(O(n\log n)\) 是预处理（排序+前缀和计算），记 \(W\) 的取值范围为 \(C=10^6\)(\(W\) 最大值即矿石最大质量), 二分次数为 \(\log C\), 每次二分需要 \(O(n)\) 预处理出前缀和数组，然后查询 \(m\) 个区间，每个区间只需 \(O(1)\) 共计 \(O(m)\)，这个时间复杂度如果不卡常数是可以顺利通过的。

解答代码

注意要开 long long 不然 s 会溢出

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
#include <cstdio>
#include <iostream>
using namespace std;

const int MAX_VAL = 200007;
int n, m, x, y;
long long s;
int w[MAX_VAL], v[MAX_VAL], pleft[MAX_VAL], pright[MAX_VAL];
long long pre_n[MAX_VAL], pre_v[MAX_VAL];

void redir() {
    freopen("luogu.in", "r", stdin);
//    freopen("out.txt", "w", stdout);
}

long long check(int pw) {
    // 计算校验和
    long long ans = 0;
    // 先预处理出前缀数组;
    pre_n[0] = 0; pre_v[0] = 0;
    for (int i = 0; i < n; ++i) {
        pre_n[i + 1] = pre_n[i] + (w[i] >= pw ? 1 : 0);
        pre_v[i + 1] = pre_v[i] + (w[i] >= pw ? v[i] : 0);
    }
    // 对每个区间计算
    for (int i = 0; i < m; ++i) {
        int l = pleft[i] - 1, r = pright[i] - 1;
        ans += (pre_n[r + 1] - pre_n[l]) * (pre_v[r + 1] - pre_v[l]);
    }
    return ans;
}

int main() {

    // redir();

    scanf("%d%d%lld", &n, &m, &s);
    // 读数据
    x = 1000007; y = 0;
    for (int i = 0; i < n; ++i) {
        scanf("%d%d", &w[i], &v[i]);
        x = min(x, w[i]); y = max(y, w[i]);
    }
    for (int i = 0; i < m; ++i) {
        scanf("%d%d", &pleft[i], &pright[i]);
    }
    // 二分 W
    long long y1, y2;
    int l = x - 1, r = y + 1;
    // 先查找不小于 s 的最小值
    while (l < r) {
        int mid = (l + r + 1) >> 1;
        if (check(mid) >= s) l = mid;
        else r = mid - 1;
    }
    y1 = check(l);
    // 再查找不大于 s 的最大值
    for (r = y + 1; l < r; ) {
        int mid = (l + r) >> 1;
        if (check(mid) > s) l = mid + 1;
        else r = mid;
    }
    y2 = check(l);
    printf("%lld\n", min(y1 - s, s - y2));
    return 0;
}

P1083 [NOIP2012 提高组] 借教室

题目描述

在大学期间，经常需要租借教室。大到院系举办活动，小到学习小组自习讨论，都需要向学校申请借教室。教室的大小功能不同，借教室人的身份不同，借教室的手续也不一样。

面对海量租借教室的信息，我们自然希望编程解决这个问题。

我们需要处理接下来 \(n\) 天的借教室信息，其中第 \(i\) 天学校有 \(r_i\) 个教室可供租借。共有 \(m\) 份订单，每份订单用三个正整数描述，分别为 \(d_j,s_j,t_j\)，表示某租借者需要从第 \(s_j\) 天到第 \(t_j\) 天租借教室（包括第 \(s_j\) 天和第 \(t_j\) 天），每天需要租借 \(d_j\) 个教室。

我们假定，租借者对教室的大小、地点没有要求。即对于每份订单，我们只需要每天提供 \(d_j\) 个教室，而它们具体是哪些教室，每天是否是相同的教室则不用考虑。

借教室的原则是先到先得，也就是说我们要按照订单的先后顺序依次为每份订单分配教室。如果在分配的过程中遇到一份订单无法完全满足，则需要停止教室的分配，通知当前申请人修改订单。这里的无法满足指从第 \(s_j\) 天到第 \(t_j\) 天中有至少一天剩余的教室数量不足 \(d_j\) 个。

现在我们需要知道，是否会有订单无法完全满足。如果有，需要通知哪一个申请人修改订单。

输入格式

第一行包含两个正整数 \(n,m\)，表示天数和订单的数量。

第二行包含 \(n\) 个正整数，其中第 \(i\) 个数为 \(r_i\)，表示第 \(i\) 天可用于租借的教室数量。

接下来有 \(m\) 行，每行包含三个正整数 \(d_j,s_j,t_j\)，表示租借的数量，租借开始、结束分别在第几天。

每行相邻的两个数之间均用一个空格隔开。天数与订单均用从 \(1\) 开始的整数编号。

输出格式

如果所有订单均可满足，则输出只有一行，包含一个整数 \(0\)。否则（订单无法完全满足）

输出两行，第一行输出一个负整数 \(-1\)，第二行输出需要修改订单的申请人编号。

样例 #1

样例输入 #1

1
2
3
4
5
4 3 
2 5 4 3 
2 1 3 
3 2 4 
4 2 4

样例输出 #1

1
2
-1 
2

提示

【输入输出样例说明】

第 $1 $份订单满足后，$4 $天剩余的教室数分别为 \(0,3,2,3\)。第 \(2\) 份订单要求第 $2 $天到第 \(4\) 天每天提供$ 3 $个教室，而第 \(3\) 天剩余的教室数为$ 2$，因此无法满足。分配停止，通知第\(2\) 个申请人修改订单。

【数据范围】

对于10%的数据，有\(1≤ n,m≤ 10\)；

对于30%的数据，有\(1≤ n,m≤1000\)；

对于 70%的数据，有\(1 ≤ n,m ≤ 10^5\)；

对于 100%的数据，有\(1 ≤ n,m ≤ 10^6,0 ≤ r_i,d_j≤ 10^9,1 ≤ s_j≤ t_j≤ n\)。

NOIP 2012 提高组 第二天 第二题

2022.2.20 新增一组 hack 数据

解题思路

最简单的思路莫过于模拟，时间复杂度为 \(O(mn)\)，但显然无法通过

注意到主要问题在每个订单都要 \(O(n)\) 的代价处理，太慢了，这里区间处理可以用线段树解决，可以提高到 \(O(m \log n)\)，但懒得写线段树...

实话说感觉如果没有标签我可能很难想到二分，因为没有二段性。二分的处理方法是，首先利用差分的方法可以 \(O(1)\) 就完成区间修改，但要检测修改后是否满足还是需要 \(O(n)\), 所以我们不每次分配后都检查，而是使用二分的方法来检查。时间复杂度 \(O((n + m) \log m)\).

但感觉这个方法有个问题是：如果越过某个订单的时间后又满足了呢？

题解中解释是：而在这个题里，因为如果前一份订单都不满足，那么之后的所有订单都不用继续考虑；而如果后一份订单都满足，那么之前的所有订单一定都可以满足，符合局部舍弃性，所以可以二分订单数量。

好吧，我弄清楚了，我理解错了维度，实际上问题中没有借教室的“时间”维度，问题其实是二维的，我想当然的认为是三维的所以认为二分不可行。可以换个理解方法：有 n 栋楼，每个订单要在 \([l,r]\) 编号楼内借 \(d\) 间教室，借了就不还了

其实还有个小优化，将差分数组做成一个时间上双向移动动态数组而不是每次清零重新计算，可以将 \(\log m\) 次每次 \(O(n)\) 降低到均摊 \(O(n)\)，总时间复杂度为 \(n + m \log m\), 不过由于 \(n, m\) 是同一数量级的，这个优化只是常数级别优化，影响不大

解答代码

模拟

时间复杂度为 \(O(mn)\), 得分 45，剩下的全部 TLE 了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include <cstdio>
#include <iostream>
using namespace std;

#define ll long long

const int N = 1000007;
int n, m, r, d, s, t;
ll room[N];


int main() {
    scanf("%d%d", &n, &m);
    for (int i = 0; i < n; ++i) {
        scanf("%lld", &room[i]);
    }
    bool succ = true;
    for (int i = 0; i < m; ++i) {
        scanf("%d%d%d", &d, &s, &t);
        for (int j = s; j <= t; ++j) {
            if (room[j - 1] < d) {
                printf("-1\n%d", i + 1);
                succ = false;break;
            }
            room[j - 1] -= d;
        }
        if (!succ) break;
    }
    if (succ) printf("0");

    return 0;
}

差分+二分

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;

#define ll long long

const int N = 1000007;
int n, m, r;
ll room[N], diff[N], d[N], s[N], t[N];

bool check(int day) {
    memset(diff, 0, sizeof(diff));
    for (int i = 0; i < day; ++i) {
        diff[s[i] - 1] += d[i];
        diff[t[i]] -= d[i];
    }
    ll cnt = 0;
    for (int i = 0; i < n; ++i) {
        cnt += diff[i];
        if (cnt > room[i]) return false;
    }
    return true;
}


int main() {

    scanf("%d%d", &n, &m);
    for (int i = 0; i < n; ++i) {
        scanf("%lld", &room[i]);
    }
    for (int i = 0; i < m; ++i) {
        scanf("%lld%lld%lld", &d[i], &s[i], &t[i]);
    }
    int left = 1, right = m + 1;
    while (left < right) {
        int mid = (left + right) >> 1;
        if (check(mid)) left = mid + 1;
        else right = mid;
    }
    if (left == m + 1) printf("0");
    else printf("-1\n%d", left);
    return 0;
}

P4343 [SHOI2015]自动刷题机

题目背景

曾经发明了信号增幅仪的发明家 SHTSC 又公开了他的新发明：自动刷题机——一种可以自动 AC 题目的神秘装置。

题目描述

自动刷题机刷题的方式非常简单：首先会瞬间得出题目的正确做法，然后开始写程序。每秒，自动刷题机的代码生成模块会有两种可能的结果：

1.写了 \(x\) 行代码
2.心情不好，删掉了之前写的 \(y\) 行代码。（如果 \(y\) 大于当前代码长度则相当于全部删除。）

对于一个 OJ，存在某个固定的正整数长度 \(n\)，一旦自动刷题机在某秒结束时积累了大于等于 \(n\) 行的代码，它就会自动提交并 AC 此题，然后新建一个文件（即弃置之前的所有代码）并开始写下一题。SHTSC 在某个 OJ 上跑了一天的自动刷题机，得到了很多条关于写代码的日志信息。他突然发现自己没有记录这个 OJ 的 \(n\) 究竟是多少。所幸他通过自己在 OJ 上的 Rank 知道了自动刷题机一共切了 \(k\) 道题，希望你计算 \(n\) 可能的最小值和最大值。

输入格式

第一行两个整数 \(l , k\)，表示刷题机的日志一共有 \(l\) 行，一共了切了 \(k\) 题。

接下来 \(l\) 行，每行一个整数 \(x_i\)，依次表示每条日志。若 \(x_i \geq 0\)，则表示写了 \(x_i\) 行代码，若 \(x_i \lt 0\)，则表示删除了 \(-x_i\) 行代码。

输出格式

输出一行两个整数，分别表示 \(n\) 可能的最小值和最大值。
如果这样的 \(n\) 不存在，请输出一行一个整数 \(-1\)。

样例 #1

样例输入 #1

1
2
3
4
5
4 2
2
5
-3
9

样例输出 #1

1
3 7

提示

数据规模与约定

  • 对于 \(20\%\) 的数据，保证 \(l \le 10\)；
  • 对于 \(40\%\) 的数据，保证 \(l \le 100\) ；
  • 对于 \(60\%\) 的数据，保证\(l \le 2 \times 10^3\)；
  • 对于 \(100\%\) 的数据，保证 \(1 \leq l \le 10^5\)，\(-10^9 \le x_i \le 10^9\)。

解题思路

显然，想要直接推断 \(n\) 的值是困难的，但如果知道 \(n\) 求切题次数 \(k\) 却很简单。

另一方面，显然有 \(n\) 越大，\(k\) 越小，因为题目要求代码越多，那么满足代码数量 \(\ge n\) 的时刻必然越少，\(k\) 也就越小。

结合上述两点结论，使用二分法也就是自然而然的了

先用二分法求最小值，然后再二分求最大值，很常规的二分操作了，接下来我们考虑 \(n\) 的取值范围是什么，毫无疑问最小值是 1，而最大值应该是代码中可能的最大行数，此时 \(k\) 可能取得最小值 1，题目没说 \(k\) 的取值范围，但 \(k\) 不可能是 0，因为 \(k\) 为 0那么 \(n\) 没有上界。

解答代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;

#define ll long long
const int N = 100007;
int length, k;
ll code[N];

int check(ll w) {
    // 计算切题数
    int cnt = 0;
    ll pre = 0;
    for (int i = 0; i < length; ++i) {
        pre = max(0ll, pre + code[i]);
        if (pre >= w) {
            ++cnt; pre = 0;
        }
    }
    return cnt;
}

int main() {
    memset(code, 0, sizeof(code));
    scanf("%d%d", &length, &k);
    // 读入数据同时测测 n 的上界
    ll bound = 0, cnt = 0;
    for (int i = 0; i < length; ++i) {
        scanf("%lld", &code[i]);
        cnt = max(0ll, cnt + code[i]);
        bound = max(cnt, bound);
    }
    // 第一次先搜索 n 的最小值
    ll left = 1, right = bound;
    while (left < right) {
        ll mid = (left + right) >> 1;
        // 注意 n 越小 k 越大，所以这里要增大 n
        if (check(mid) > k) left = mid + 1;
        else right = mid;
    }
    if (check(left) != k) {
        printf("-1");
        return 0;
    }
    printf("%lld", left);
    // 接下来搜索 n 的最大值
    for (right = bound; left < right; ) {
        ll mid = (left + right + 1) >> 1;
        if (check(mid) < k) right = mid - 1;
        else left = mid;
    }
    printf(" %lld", left);
    return 0;
}

总结

注意到二分一般用在区间搜索，在这些题目中都有个比较显著的特点，那就是根据题目求解答案都很困难，但若已知答案验证答案是否合理却比较简单，同时还具备二分所必须的二段性，所以都能采用类似 猜数字 这样的方法来搜索答案。

--- ♥ end ♥ ---

欢迎关注我呀~