六、倍增

6.1 天才ACM (二分、倍增、归并)

ACwing 109

题解参考

算法1：贪心+二分 (TLE)
时间复杂度$O(n^{2}lo{g}^n)$

首先，根据校验值的定义，要快速求出校验值，首先想到的办法肯定是贪心：将 $S$ 排序，每次取到 $S$ 中的最大值和最小值，最后计算出来的结果即为 $S$ 的校验值。

证明：证明四个数的情况，多个数同理。设这四个数为$a、b、c、d$，且$0<a\le b\le c\le d$，只需要证明$$(d-a{)}^2+(c-b{)}^2\ge (c-a{)}^2+(d-b{)}^2$$因为$a\le b、c\le d$，有
⇒ ( b − a ) d ≥ ( b − a ) c ⇒ b d − a d ≥ b c − a c ⇒ b d + a c ≥ b c + a d ⇒ − 2 b c − 2 a d ≥ − 2 b d − 2 a c ⇒ a 2 + b 2 + c 2 + d 2 − 2 b c − 2 a d ≥ a 2 + b 2 + c 2 + d 2 − 2 b d − 2 a c ⇒ ( d − a ) 2 + ( c − b ) 2 ≥ ( c − a ) 2 + ( d − b ) 2

⇒(b−a)d≥(b−a)c⇒bd−ad≥bc−ac⇒bd+ac≥bc+ad⇒−2bc−2ad≥−2bd−2ac⇒a2+b2+c2+d2−2bc−2ad≥a2+b2+c2+d2−2bd−2ac⇒(d−a)2+(c−b)2≥(c−a)2+(d−b)2$$\begin{array}{rl}& \Rightarrow (b-a)d\ge (b-a)c\\ & \Rightarrow bd-ad\ge bc-ac\\ & \Rightarrow bd+ac\ge bc+ad\\ & \Rightarrow -2bc-2ad\ge -2bd-2ac\\ & \Rightarrow a^2+b^2+c^2+d^2-2bc-2ad\ge a^2+b^2+c^2+d^2-2bd-2ac\\ & \Rightarrow (d-a{)}^2+(c-b{)}^2\ge (c-a{)}^2+(d-b{)}^2\end{array}$$

​⇒(b−a)d≥(b−a)c⇒bd−ad≥bc−ac⇒bd+ac≥bc+ad⇒−2bc−2ad≥−2bd−2ac⇒a2+b2+c2+d2−2bc−2ad≥a2+b2+c2+d2−2bd−2ac⇒(d−a)2+(c−b)2≥(c−a)2+(d−b)2​同理可证明$(d-a{)}^2+(c-b{)}^2\ge (b-a{)}^2+(d-c{)}^2$。

求出每段区间的校验值之后，如何找到一种划分区间最少的划分方案？因为要划分的区间最少，所以要每次划分的区间尽可能长。那么我们就可以每次划分区间的时候，用二分求出当前能划分的最长的区间。

对于时间复杂度的分析：比如说最坏情况是每次区间长度只$+1$，这样计算一段就需要：$$\frac{n}{2}lo{g}^{\frac{n}{2}}+\frac{n}{4}lo{g}^{\frac{n}{4}}+...+1lo{g}^1<(\frac{n}{2}+\frac{n}{4}+...+1)lo{g}^{\frac{n}{2}}<nlo{g}^n$$所以计算一段时间复杂度为$O(nlo{g}^n)$，总共有$n$种长度，所以总共的时间复杂度为$O(n^{2}lo{g}^n)$。

#include <iostream>
#include <algorithm>

using namespace std;

typedef long long LL;

const int N = 5e5 + 10;

int n, m;
int ans; // 存储答案
LL T; // 题目中的T
LL w[N], t[N]; // w存储输入 t存储用于求校验值的数组

LL sq(LL x) { return x * x; };

// 获得数组区间[l, r]校验值
LL get(int l, int r) {
    int k = 0;
    for (int i = l; i <= r; i++) t[k++] = w[i];
    sort(t, t + k);
    LL sum = 0;
    for (int i = 0; i < m && i < k; i++, k--) sum += sq(t[i] - t[k - 1]);
    return sum;
}

int main() {
    ios ::sync_with_stdio(false);
    int K;
    cin >> K;
    while (K--) {
        cin >> n >> m >> T;
        for (int i = 0; i < n; i++) cin >> w[i];
        ans = 0;
        int start = 0; // 区间左端点
        while (start < n) {
            int l = start, r = n;
            while (l < r) {
                int mid = (l + r) >> 1;
                if (get(start, mid) > T) r = mid;
                else l = mid + 1;
            }
            start = r;
            ans++;
        }
        cout << ans << endl;
    }
    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
46
47
48
49

算法2：倍增 (AC)
时间复杂度$O(n(lo{g}^n{)}^2)$

设当前划分区间起点为 $start$：

1. 让$len=1，end=start$；
2. 每次判断区间$[start,end+start)$的校验值是否合法 (注意区间左闭右开)；
3. 如果合法，让$end=end+len$，然后$len=len\times 2$，后面重复$2$；
4. 如果不合法，让$len=\frac{len}{2}$，此时如果$len=0$，跳出循环，否则重复$2$。

时间复杂度分析：

假设答案中的每段区间长度为$le{n}_1,le{n}_2,...,le{n}_k$，对于每个$le{n}_i$，需要倍增$O(lo{g}^n)$次。对于每次找到一段，则需要$O(lo{g}^{n}le{n}_{i}lo{g}^{le{n}_i})$，所以总的时间复杂度为$$O((le{n}_{1}lo{g}^{le{n}_1}+le{n}_{2}lo{g}^{le{n}_2}+...+le{n}_{k}lo{g}^{le{n}_k})lo{g}^n)=O(n(lo{g}^n{)}^2)$$

#include <iostream>
#include <algorithm>

using namespace std;

typedef long long LL;

const int N = 5e5 + 10;

int n, m;
int ans; // 存储答案
LL T; // 题目中的T
LL w[N], t[N]; // w存储输入 t存储用于求校验值的数组

LL sq(LL x) { return x * x; };

// 获得数组区间[l, r]校验值
LL get(int l, int r) {
    int k = 0;
    for (int i = l; i < r; i++) t[k++] = w[i];
    sort(t, t + k);
    LL sum = 0;
    for (int i = 0; i < m && i < k; i++, k--) sum += sq(t[i] - t[k - 1]);
    return sum;
}

int main() {
    ios::sync_with_stdio(false);
    int K;
    scanf("%d", &K);
    while (K--) {
        scanf("%d%d%lld", &n, &m, &T);
        for (int i = 0; i < n; i++) scanf("%lld", w + i);
        ans = 0;
        int start = 0, end = 0; // 区间左端点
        while (end < n) {
            int len = 1;
            while (len) {
                if (end + len <= n && get(start, end + len) <= T)
                    end += len, len <<= 1;
                else len >>= 1;
            }
            start = end;
            ans++;
        }
        printf("%d\n", ans);
    }
    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
46
47
48
49

算法3：倍增+归并 (AC)
时间复杂度：$O(nlo{g}^n)$

在上面的代码中，处理$[start,end)$的时候，已经将$[start,end)$排好序了，所以不需要在处理$[start,end+len)$时再排序，只需要将$[end,end+len)$排序即可，然后将$[start,end)$与$[end,end+len)$两段区间进行归并即可。

时间复杂度分析：

假设一共将数组划分成了 $k$ 个区间（这里的区间指的是每次二分里面check的区间总和，并非题目中所指的区间），每个区间的长度分别为 $le{n}_1,le{n}_2,\cdots ,le{n}_k$。

那么按上述方法只需要将每个区间排序一遍，所以时间复杂度为$$O(le{n}_{1}lo{g}^{le{n}_1}+le{n}_{2}lo{g}^{le{n}_2}+\cdots +le{n}_{k}lo{g}^{le{n}_k})\le O(nlo{g}^n)$$加上每次归并的时间复杂度为$O(n)$，总的时间复杂度为$O(n+nlo{g}^n)=O(nlo{g}^n)$。

#include <iostream>
#include <algorithm>

using namespace std;

typedef long long LL;

const int N = 5e5 + 10;

int n, m;
int ans; // 存储答案
LL T; // 题目中的T
LL w[N], t[N]; // w存储输入 t存储用于求校验值的数组
LL tmp[N];

LL sq(LL x) { return x * x; };

// 判断区间 [l, r) 是否合法，并将 t 中的 [l, mid) 区间和 [mid, r) 区间合并到 tmp 中
inline bool check(int l, int mid, int r) {
    for (int i = mid; i < r; i++) t[i] = w[i];
    sort(t + mid, t + r);
    int i = l, j = mid, k = 0;
    while (i != mid && j != r) // 注意是开区间
        if (t[i] < t[j]) tmp[k++] = t[i++];
        else tmp[k++] = t[j++];
    while (i != mid) tmp[k++] = t[i++];
    while (j != r) tmp[k++] = t[j++];
    LL sum = 0;
    for (int i = 0; i < m && i < k; i++, k--)
        sum += sq(tmp[i] - tmp[k - 1]);
    return sum <= T;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int K;
    scanf("%d", &K);
    while (K--) {
        scanf("%d%d%lld", &n, &m, &T);
        for (int i = 0; i < n; i++) scanf("%lld", w + i);
        ans = 0;
        int len;
        int start = 0, end = 0;
        while (end < n) {
            len = 1;
            while (len) {
                if (len + end <= n && check(start, end, end + len)) {
                    end += len, len <<= 1;
                    if (end >= n) break;
                    /*// 在 check 时，已经将 t 数组的 [start, end + len) 这段区间归并在 tmp 中了。现在只需要将 tmp 中的有序数组复制到 t 中即可*/
                    for (int i = start; i < end; i++)
                        t[i] = tmp[i - start]; // tmp 是从 0 开始存的，t 是从 start 开始存的
                } else len >>= 1;
            }
            start = end;
            ans++;
        }
        printf("%d\n", ans);
    }
    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
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63

七、贪心

7.1 防晒

ACwing 110

题目含义为：有若干个区间和若干个点，如果这个点包含在该区间内部(包括端点)，那么这个区间和这个点匹配。题目问：最多可以选择多少个这样的匹配关系？

算法思路：

先将所有区间按照区间起点从大到小排序，从前往后依次扫描，在能够选择的所有点中，选择能选择的、在当前扫描区间内部的、值最大的点。扫描完之后，该题解为能匹配上点的区间的数量。

增广路径：在二分图中，先从左边非匹配点走，先走非匹配边，然后沿着匹配边，非匹配边、匹配边、非匹配边、匹配边…，最终走到右边一个非匹配点。如果存在这样一条路径，那么可以将所有匹配边删去，留下所有的非匹配边形成匹配边，且原非匹配边的数量比原匹配边的数量多1。

算法正确性证明：
如果将所有的每个区间和每个点都看做一个点，分成两列，那么该问题就相当于是一个二分图的最大匹配问题。我们知道二分图的最大匹配等价于图中不存在增广路径。

下面这一段解释参考题解

我们首先将奶牛可以承受的最小值，递减排序，也就是降序排列，然后将防晒霜固定的值，递减排序，还是降序排列。

对于每一个头奶牛而言，当然是要选择目前来说满足条件的最差的防晒霜，什么最差的定义，就是选择满足奶牛条件的SPF最大的那一瓶防晒霜。

注意：降序排序，保证对于每一头牛而言，它用的是，可以使用的最差的防晒霜，因为值越小的防晒霜，有可能让更多的牛使用。而升序排列，就恰好反了。

#include <iostream>
#include <algorithm>
#include <map>

using namespace std;

typedef pair<int, int> PII;

const int N = 2510;

int n, m;
PII cow[N];
map<int, int> spfs;

int main() {
    cin >> n >> m;
    for (int i = 0; i < n; i++) cin >> cow[i].first >> cow[i].second;
    for (int i = 0; i < m; i++) {
        int spf, cover; cin >> spf >> cover;
        spfs[spf] += cover;
    }
    sort(cow, cow + n);
    int res = 0;
    spfs[0] = spfs[1001] = n;
    for (int i = n - 1; i >= 0; i--) {
        auto spf = spfs.upper_bound(cow[i].second);
        spf--;
        if (spf->first >= cow[i].first && spf->first <= cow[i].second) { // 在区间内部
            res++;
            if (--spf->second == 0) spfs.erase(spf);
        }
    }
    cout << res << endl;
    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

7.2 畜栏预定 (区间分组)

ACwing 111

思路见：基础算法_基础篇_贪心_区间分组

#include <iostream>
#include <algorithm>
#include <queue>

#define x first
#define y second

using namespace std;

typedef pair<int, int> PII;

const int N = 50010;

int n;
int id[N]; // 第i头奶牛对应的畜栏
pair<PII, int> cows[N]; // 区间，奶牛编号

bool cmp(const pair<PII, int> &a, const pair<PII, int> &b) { return a.x.x < b.x.x; }

int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf("%d%d", &cows[i].x.x, &cows[i].x.y);
        cows[i].y = i;
    }
    sort(cows, cows + n, cmp);
    priority_queue<PII, vector<PII>, greater<PII>> heap; // 当前分组内右端点最大值 ：分组编号
    for (int i = 0; i < n; i++) 
        if (heap.empty() || heap.top().x >= cows[i].x.x) {
            PII stall = {cows[i].x.y, heap.size()};
            id[cows[i].y] = stall.y;
            heap.push(stall);
        } else {
            auto stall = heap.top(); heap.pop();
            stall.x = cows[i].x.y;
            id[cows[i].y] = stall.y;
            heap.push(stall);
        }
    printf("%d\n", heap.size());
    for (int i = 0; i < n; i++) printf("%d\n", id[i] + 1);
    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

7.3 雷达设备 (区间选点)

ACwing 112

#include <iostream>
#include <algorithm>
#include <cmath>

#define x first
#define y second

using namespace std;

typedef pair<double, double> PDD;

const int N = 1010;
const double eps = 1e-6, INF = 1e10;

int n, d;
PDD seg[N];

int main() {
    scanf("%d%d", &n, &d);
    bool success = true;
    for (int i = 0; i < n; i++) {
        int x, y;
        scanf("%d%d", &x, &y);
        if (y > d) { success = false; break; }
        double len = sqrt(d * d - y * y);
        seg[i] = {x + len, x - len}; // 右端点 : 左端点
    }
    if (!success) { puts("-1"); return 0; }
    sort(seg, seg + n);
    int res = 0;
    double last = -INF;
    for (int i = 0; i < n; i++)
        if (seg[i].y > last + eps) 
            res++, last = seg[i].x;     
    printf("%d\n", res);
    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

7.4 国王游戏

ACwing 114

该算法思想与 9.10耍杂技的牛 方法类似，这个题是乘法，那个题为加法。

算法思路：

将所有的大臣按照其左手和右手上的数的乘积从小到大排序，排序之后，获得奖赏最多的大臣，其所获得的奖赏就为最大值。

时间复杂度：

• 排序是$O(nlo{g}^n)$
• 高精度计算，每个数最大为$A_i=9999$，则前$i$个数的乘积大约为$4i$位，每一次乘以一个新的数就要$4i$的计算量，所以总的计算量为$O(4{\sum }_{i=1}^{n}i)=O(n^2)$。

因此总的时间复杂度为$O(n^2)$。

算法正确性证明：
假设存在第$i$个和第$i+1$个大臣，他们左手里的数字分别记为$A_i、A_{i+1}$，右手里的数字记为$B_i、B_{i+1}$，并且有$A_i\times B_i\ge A_{i+1}\times B_{i+1}$，现在将第$i$个和第$i+1$个人手里的数据交换，再计算两者手里的奖赏值。记交换前两者手里的奖赏值为$S_i、S_{i+1}$，交换后两者手里的奖赏值为${S_i}^{\prime }、{S_{i+1}}^{\prime }$，那么有 S i = A 1 × A 2 × . . . × A i − 1 B i S i + 1 = A 1 × A 2 × . . . × A i B i + 1 S i ′ = A 1 × A 2 × . . . × A i − 1 B i + 1 S i + 1 ′ = A 1 × A 2 × . . . × A i − 1 × A i + 1 B i

SiSi+1Si′Si+1′=A1×A2×...×Ai−1Bi=A1×A2×...×AiBi+1=A1×A2×...×Ai−1Bi+1=A1×A2×...×Ai−1×Ai+1Bi$$\begin{array}{rl}{S}_i& =\frac{A_1\times A_2\times ...\times A_{i-1}}{B_i}\\ S_{i+1}& =\frac{A_1\times A_2\times ...\times A_i}{B_{i+1}}\\ {S_i}^{\prime }& =\frac{A_1\times A_2\times ...\times A_{i-1}}{B_{i+1}}\\ {S_{i+1}}^{\prime }& =\frac{A_1\times A_2\times ...\times A_{i-1}\times A_{i+1}}{B_i}\end{array}$$

Si​Si+1​Si​′Si+1​′​=Bi​A1​×A2​×...×Ai−1​​=Bi+1​A1​×A2​×...×Ai​​=Bi+1​A1​×A2​×...×Ai−1​​=Bi​A1​×A2​×...×Ai−1​×Ai+1​​​将上见面所有数都乘以$\frac{B_i\times B_{i+1}}{A_1\times A_2\times ...\times A_{i-1}}$，则有 S i = B i + 1 S i + 1 = A i B i S i ′ = B i S i + 1 ′ = A i + 1 B i + 1

SiSi+1Si′Si+1′=Bi+1=AiBi=Bi=Ai+1Bi+1$$\begin{array}{rl}{S}_i& =B_{i+1}\\ S_{i+1}& =A_i{B}_i\\ {S_i}^{\prime }& =B_i\\ {S_{i+1}}^{\prime }& =A_{i+1}{B}_{i+1}\end{array}$$

Si​Si+1​Si​′Si+1​′​=Bi+1​=Ai​Bi​=Bi​=Ai+1​Bi+1​​因为$0<A_i,B_i<10000$且$A_i,B_i\in N_{+}$，所以有$S_{i+1}>{S_i}^{\prime }$，又因为已知$S_{i+1}=A_i{B}_i\ge {S_{i+1}}^{\prime }=A_{i+1}{B}_{i+1}$，所以$S_{i+1}>max({S_i}^{\prime },{S_{i+1}}^{\prime })$，也有$max(S_i,S_{i+1})>max({S_i}^{\prime },{S_{i+1}}^{\prime })$，故当两个大臣左手和右手里数字乘积为逆序的时候，交换两者手中的值并不会使其手里的奖赏值增加，所以最优解应该为：将所有的大臣按照其左手和右手上的数的乘积从小到大排序，排序之后，获得奖赏最多的大臣，其所获得的奖赏就为最大值。

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

typedef pair<int, int> PII;

const int N = 1010;

int n;
PII p[N];

// 高精度乘法
vector<int> mul(vector<int> a, int b) {
    vector<int> c;
    int t = 0;
    for (int i = 0; i < a.size(); i++) {
        t += a[i] * b;
        c.push_back(t % 10);
        t /= 10;
    }
    while (t) {
        c.push_back(t % 10);
        t /= 10;
    }
    return c;
}

// 高精度除法
vector<int> div(vector<int> a, int b) {
    vector<int> c;
    bool is_first = true;
    for (int i = a.size() - 1, t = 0; i >= 0; i--) {
        t = t * 10 + a[i];
        int x = t / b;
        if (!is_first || x) {
            is_first = false;
            c.push_back(x);
        }
        t %= b;
    }
    reverse(c.begin(), c.end());
    return c;
}

// 求出最大值
vector<int> max_vec(vector<int> a, vector<int> b) {
    if (a.size() > b.size()) return a;
    if (a.size() < b.size()) return b;
    if (vector<int>(a.rbegin(), a.rend()) > vector<int>(b.rbegin(), b.rend())) return a;
    return b;
}

int main() {
    cin >> n;
    for (int i = 0; i <= n; i++) { // i=0 为国王
        int a, b; cin >> a >> b;
        p[i] = {a * b, a};
    }
    sort(p + 1, p + n + 1); // 排除掉国王

    vector<int> product(1, 1); // 大臣前面所有人左手上的数的乘积

    vector<int> res(1, 0);
    for (int i = 0; i <= n; i++) {
        if (i) res = max_vec(res, div(product, p[i].first / p[i].second));
        product = mul(product, p[i].second);
    }

    for (int i = res.size() - 1; i >= 0; i--) cout << res[i];
    cout << endl;

    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
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75

7.5 给树染色

八、RMQ\ST表\跳表

RMQ（Range Minimum/Maximum Query），即区间最值查询，RMQ算法一般用较长时间做预处理，时间复杂度为$O(nlo{g}^n)$，然后可以在$O(1)$的时间内处理每次查询。

缺点：无法修改值。

预处理：动态规划

设$f(i,j)$表示从$i$开始，长度为$2^j$的区间中的最大值。将区间$[i,i+2^j-1]$分成两个部分，有$[i,2^{j-1}]、[i+2^{j-1},2^{j-1}]$。要求整个区间上的最大值，就需要求这两个小区间上的最大值，因此有地推公式： f ( i , j ) = m a x { f ( i , j − 1 ) ,   f ( i + 1 < < ( j − 1 ) , j − 1 } f(i,j) = max\{f(i, j - 1), \space f(i + 1 << (j-1), j -1\} f(i,j)=max{f(i,j−1), f(i+1<<(j−1),j−1}第一维有$n$个状态，第二维有$lo{g}^n$个状态，状态转移$O(1)$，因此整个时间复杂度为$O(nlo{g}^n)$。

求区间最值：

假设存在区间$[L,R]$，其长度为$len$，若存在一个使$2^k\le len$的最大整数$k$，则有$2\times 2^k>len$，因此区间$[L,R]$上的最大值即为 m a x { f ( L , k ) ,   f ( R − 2 k + 1 , k ) } max\{f(L, k), \space f(R - 2^k + 1, k)\} max{f(L,k), f(R−2k+1,k)}其中$k=\lfloor lo{g}_2^{len}\rfloor =\lfloor \frac{lo{g}_{10}^{len}}{lo{g}_{10}^2}\rfloor$。

• $lo{g}_x^y=\frac{lo{g}_c^y}{lo{g}_c^y}$；
• C++ 中的库函数$log$是以$e$为底，$log2$是以$2$为底，$log10$是以$10$为底；
• C++ 中 $e$ 的表示：使用库函数$exp(intx)$表示$e^x$。

8.1 天才的记忆

ACwing 1273

#include <cstdio>
#include <algorithm>
#include <cmath>

using namespace std;

const int N = 200010, M = 18;

int n, m;
int w[N], f[N][M];

void init() {
    for (int j = 0; j < M; j++) // 区间长度
        for (int i = 1; i + (1 << j) - 1 <= n; i++) // 要保证当前区间右端点不能超过整个区间的最右端
            if (!j) f[i][j] = w[i]; // 只有一个数
            else f[i][j] = max(f[i][j - 1], f[i + (1 << (j - 1))][j - 1]);
}

int query(int l, int r) {
    int k = log(r - l + 1) / log(2); // 返回k为int，强制向下取整
    return max(f[l][k], f[r - (1 << k) + 1][k]);
}

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) scanf("%d", w + i);
    init(); // 预处理
    scanf("%d", &m);
    while (m--) {
        int l, r; scanf("%d%d", &l, &r);
        printf("%d\n", query(l, r));
    }
    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

九、总结与联系

9.1 飞行员兄弟

ACwing 116

首先，应该知道这个题同一个位置操作两次没有意义。

对于$16\times 16$个开关，每一个开关只有按或者不按两种状态，所以总共有$2^{16}$种状态。每一种方案都操作$16$个开关，所以总共时间复杂度为$O(16\times 2^{16})$。

对于每个开关，可以预先处理出该位置上每一行和每一列所表示出来的十进制数change[i][j]，然后对其进行进行change[i][j]^state即可，如下图所示。

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

typedef pair<int, int> PII;
const int N = 4;

int change[N][N];

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

int main() {
    for (int i = 0; i < N; i++)
        for (int j = 0; j < N; j++) {
            for (int k = 0; k < N; k++) change[i][j] += (1 << get(i, k)) + (1 << get(k, j));
            change[i][j] -= 1 << get(i, j); // (i,j)位置被加了两次，要减去一次
        }

    int state = 0;
    for (int i = 0; i < N; i++) {
        string line; cin >> line;
        for (int j = 0; j < N; j++)
            if (line[j] == '+')
                state += 1 << get(i, j);
    }

    vector<PII> path, temp;
    for (int i = 0; i < 1 << 16; i++) {
        int now = state;
        temp.clear();
        for (int j = 0; j < 16; j++)
            if (i >> j & 1) {
                int x = j / 4, y = j % 4;
                now ^= change[x][y];
                temp.push_back({x, y});
            }
        if (!now && (path.empty() || path.size() > temp.size())) path = temp;
    }

    cout << path.size() << endl;
    for (auto &p: path) cout << p.first + 1 << ' ' << p.second + 1 << endl;

    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

9.2 占卜DIY

ACwing 117

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

vector<int> closed[14];
int open[14];

int main() {
    for (int i = 1; i <= 13; i ++ ) 
        for (int j = 0; j < 4; j ++ ) {
            int x; char s[2];
            cin >> s;
            if (*s >= '2' && *s <= '9') x = *s - '0';
            else if (*s == '0') x = 10;
            else if (*s == 'A') x = 1;
            else if (*s == 'J') x = 11;
            else if (*s == 'Q') x = 12;
            else x = 13;
            closed[i].push_back(x);
        }
    
    for (int i = 0; i < 4; i ++ ) {
        int t = closed[13][i];
        while (t != 13) {
            open[t] ++ ;
            int r = t;
            t = closed[r].back();
            closed[r].pop_back();
        }
    }
    
    int res = 0;
    for (int i = 1; i <= 12; i ++ ) res += open[i] >= 4;
    cout << res << endl;
    
    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

9.3 分形

ACwing 118

#include <iostream>
#include <algorithm>
using namespace std;

const int N = 1010;

char g[N][N];

void dfs(int n) {
    if (n == 1) {
        g[0][0] = 'X';
        return;
    }

    dfs(n - 1);

    int len = 1;
    for (int i = 0; i < n - 2; i++) len *= 3; // n-1 级图形的边长

    // 该级图形出左上角图形之外其余4个部分左上角坐标
    int sx[4] = {0, 1, 2, 2}, sy[4] = {2, 1, 0, 2};

    for (int k = 0; k < 4; k++)
        for (int i = 0; i < len; i++)
            for (int j = 0; j < len; j++)
                g[sx[k] * len + i][sy[k] * len + j] = g[i][j];
}

int main() {
    dfs(7);
    int n;
    while (cin >> n, n != -1) { // 已经预处理了7级图形，如果要输出k即，只需要输出7级图形的左上角即可
        int k = 1; // 求出该级图形长度
        while (--n) k *= 3;

        for (int i = 0; i < k; i++) {
            for (int j = 0; j < k; j++)
                if (g[i][j]) cout << g[i][j];
                else cout << ' ';
            cout << endl;
        }
        cout << '-' << endl;
    }
    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

9.4 袭击

ACwing 119

这个题目的代码可能会TLE，但是应该学习解决问题 求一对距离最近的点的距离 的方法。

先考虑简单情况：假设图中有$n$个点，求其中一对距离最近的点的距离。

算法思路(分治)：先将所有点按横坐标从小到大排序，然后选择一条竖线$x_0$将图中的所有点平均分成两部分，横坐标小于$x_0$的点在左边，横坐标大于$x_0$的点在右边。然后分三种情况求解：

1. 所有点在左边，它们之间距离最小的一对点；
2. 所有点在右边，它们之间距离最小的一对点；
3. 当一个点在左边，一个点在右边的时候，它们之间距离最小的一对点；

对上面三种情况所获得的距离取$min$即为答案。

如何在$O(n)$的时间复杂度内计算出第三种情况？
假设通过计算得到情况$1$和情况$2$中的最小距离记为$\delta$，考虑左边和右边最靠近划分区间的实线$x_0$的一对划分区间。

也就是说这两个区间是最初划分区间的那根轴$x_0$两边的、在最终划分完区间之后，左右两边分别最靠近划分轴$x_0$的区间。如果取其它的两个区间，那么分别取两个区间内部的一对点的距离一定会大于$\delta$。

若其区间长度为$\delta$，则对左边区间内部的任意一个点，以该点为圆心、半径为$\delta$做圆，该圆内部且在右半区间的点即为可能形成的一对距离更小的点，如图所示。

如果对每一个左边区间内部的点考虑最坏的情况，即当圆心在划分轴上的时候，那么可能小于$\delta$的另一个点就只能在阴影半圆内部。但是半圆不方便分析，所以将其扩展成一个长方形，如图中紫色矩形。

首先在矩形中不可能存在一对点，其距离比$\delta$更小。可以从图中知道矩形的边长分别为$2\delta 、3\delta$，并且可以证明在矩形内部最多只有$6$个点，其与左边区间点的距离可能小于$\delta$。

如下图所示，将其划分为$6$个小矩形，那么每个小矩形的长宽分别为$\frac{\delta }{2}、\frac{2\delta }{3}$，且小矩形内部两个点之间的最大距离为$\sqrt{(\frac{\delta }{2}{)}^2+(\frac{2\delta }{3}{)}^2}<\delta$，$6$个点分别落在每个小矩形中。假设在矩形内部存在$7$个点，那么必有一个小矩形内部至少存在两个点，那么这两个点之间的距离${\delta }^{\prime }<\delta$，矛盾。因此，对于左边区间任意一个点而言，最多只需考虑$6$个右边的点。

因此，可以先计算完情况$1$和情况$2$后，求出二者最小值$\delta$，然后在左边和右边所有点中，将所有距离中间划分实轴小于等于$\delta$的点取出，放在集合$S$中，并按照纵坐标从上到下排序，对于每个点而言，假设其纵坐标为$y_0$，我们仅考虑集合$S$中，纵坐标在$y_0\pm \delta$之间的，这样的点最多只有$6$个。

这里的排序，为了节省时间复杂度，可以在递归的时候按纵坐标排序(类似于归并排序)，然后需要得到整个有序序列的时候可以按照归并排序的思路，这样时间复杂度就从$O(logn)$降为$O(n)$。

对于这个题，计算两种点之间的最短距离，只需要考虑当两个点的类型相同，使它们之间的距离为$INF$即可。

时间复杂度：分治$logn$层，每层时间复杂度为$O(n)$，总的时间复杂度为$O(nlogn)$。

#include <iostream>
#include <algorithm>
#include <cmath>

using namespace std;

const int N = 200010, INF = 1e10;

struct Point {
    double x, y;
    bool type;
    bool operator<(const Point &W) const { return x < W.x; }
} points[N], temp[N];

double dist(Point a, Point b) {
    if (a.type == b.type) return INF;
    double dx = a.x - b.x, dy = a.y - b.y;
    return sqrt(dx * dx + dy * dy);
}

double dfs(int l, int r) {
    if (l >= r) return INF; // 当前区间最多只有1个元素

    int mid = (l + r) >> 1;
    double mid_x = points[mid].x; // 分界线
    double res = min(dfs(l, mid), dfs(mid + 1, r));

    { // 归并排序
        int k = 0, i = l, j = mid + 1;
        while (i <= mid && j <= r)
            if (points[i].y < points[j].y) temp[k++] = points[i++];
            else temp[k++] = points[j++];
        while (i <= mid) temp[k++] = points[i++];
        while (j <= r) temp[k++] = points[j++];

        for (i = 0, j = l; i < k; i++, j++) points[j] = temp[i];
    }

    // 将对称轴左右两个区间的点加进来
    int k = 0;
    for (int i = l; i <= r; i++)
        if (points[i].x >= mid_x - res && points[i].x <= mid_x + res)
            temp[k++] = points[i];

    // 枚举区间内部的点
    for (int i = 0; i < k; i++)
        for (int j = i - 1; j >= 0 && temp[i].y - temp[j].y < res; j--)
            res = min(res, dist(temp[i], temp[j]));

    return res;
}

int main() {
    int T, n; cin >> T;
    while (T--) {
        scanf("%d", &n);
        for (int i = 0; i < n; i++) { // 红色点
            scanf("%lf%lf", &points[i].x, &points[i].y);
            points[i].type = 0;
        }
        for (int i = n; i < 2 * n; i++) { // 蓝色点
            scanf("%lf%lf", &points[i].x, &points[i].y);
            points[i].type = 1;
        }

        sort(points, points + n * 2); // 按横坐标排序

        printf("%.3lf\n", dfs(0, n * 2 - 1));
    }

    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
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72

9.5 防线

ACwing 120

在数轴上，存在多个整数等差数列，每个等差数列数列上的、对应数轴上的每个位置都有一个数，记为$p$，这样数轴上的每个整数点的值为所有等差数列在该位置上的$\sum p$之和。题目保证$\sum p$为奇数的位置最多只有一个，其余所有的$p$都是偶数，如果无解即为所有的$\sum p$都是偶数。题目要求找出奇数$p$的位置。

算法思路：(前缀和 + 二分)

参考题解

1、奇数位存在性
整个序列中至多有一个位置的数字所占数量是奇数，所以如果存在奇数位，则整个数列的总和必然是奇数（奇数 + 偶数 = 奇数，偶数 + 偶数 = 偶数）。反之，若不存在奇数位，则一定是偶数。故只需判断数字数量的总和的奇偶性即可。

2、二分位置
若存在这个奇数位，就可以通过二分答案的位置来找到这个位置，然后判断区间$[l,mid]$总和的奇偶性。若为奇数，则奇数位存在于此区间。反之若为偶数，则一定存在于$[mid+1,r]$区间。用这个方法逐步缩小范围即可。对于求解区间$[l,mid]$之和，可以使用前缀和$sum[mid]-sum[l-1]$即可。

3、在$O(n)$时间内求出$sum[x]$

首先考虑对于对于一个等差数列(起点$S_i$，终点为$E_i$，公差为$D_i$)，该等差数列中在$x$左边的数有多少个：

• 如果该等差数列$S_i>x$，那么在$x$左边的数有$0$个；
• 如果该等差数列$S_i\le x$，那么在$x$左边的数为 中间间隔数目+ 1，即$$\frac{min(x,E_i)-S_i}{D_i}+1$$该时间复杂度为$O(1)$。

那么对于所有的等差数列，其在$x$左边的数的个数为$$\sum _{i=1}^n(\frac{min(x,E_i)-S_i}{D_i}+1)$$该时间复杂度为$O(n)$。

时间复杂度：

二分时间为$O(logn)$，每一次$check()$时间为$O(n)$，因此总共时间复杂度为$O(nlogn)$。

#include <cstdio>
#include <algorithm>
using namespace std;

typedef long long LL;
const int N = 2e5 + 10;

struct Seq { // 等差数列
    int s, e, d;
} seqs[N];

int n;

// x前面有多少个数
LL get_sum(int x) {
    LL res = 0;
    for (int i = 0; i < n; i++)
        if (seqs[i].s <= x)
            res += (min(seqs[i].e, x) - seqs[i].s) / seqs[i].d + 1;
    return res;
}

int main() {
    int T; scanf("%d", &T);
    while (T--) {
        int l = 0, r = 0;
        scanf("%d", &n);
        for (int i = 0; i < n; i++) {
            int s, e, d; scanf("%d%d%d", &s, &e, &d);
            seqs[i] = {s, e, d};
            r = max(r, e);
        }

        while (l < r) {
            int mid = ((LL) l + r) >> 1;
            if (get_sum(mid) & 1) r = mid;
            else l = mid + 1;
        }

        auto sum = get_sum(r) - get_sum(r - 1);
        if (sum % 2) printf("%d %lld\n", r, sum);
        else puts("There's no weakness.");
    }

    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
46

9.6 赶牛入圈

ACwing 121

题意：在平面上有多个点，每个点上有一个数值，现在在平面上找一个正方形，使得正方形中包含的数值之和至少为$C$的前提下，正方形的边长最小。

这个题目和第26次CCF CSP认证考试第二题相似，当时没有考虑离散化，也没有考虑二分，直接暴力枚举，因为是第二题，直接过了。

算法思路：(前缀和 + 离散化 + 二分)

因为牛的横纵坐标$x、y\in [1,10000]$，如果直接开一个$10000\times 10000$的数组会非常大。

首先需要对每头牛的坐标进行离散化，这里将横纵坐标放在一起做的离散化。然后获取离散化坐标的二维前缀和$sum[][]$。最后在$[1,10000]$中枚举正方形的边长，如果该正方形的前缀和大于等于$C$，则缩小边长，否则扩大边长。

代码中$chece()$函数两点解释：

• 一个是$(x1,y1)、(x2y2)$分别代表矩形左上角和右下角坐标，且是离散化之后的坐标；
• $while()$中要$+1$的原因；
• 注意理解这里的离散化，离散化之后相当于是重新建立了一个新的坐标轴，其范围为$[1,numbers.size()]$，然后在这里枚举所有的矩形，看是否存在前缀和大于等于$C$的矩形。

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

typedef pair<int, int> PII;
const int N = 1010;

int n, m;
PII points[N];
int sum[N][N]; // 离散化后的坐标对应的前缀和
vector<int> numbers; // 离散化之后的数

bool check(int len) {
    for (int x1 = 0, x2 = 1; x2 < numbers.size(); x2++) {
        while (numbers[x2] - numbers[x1 + 1] + 1 > len) x1++; // 如果x1的下一个数也不在范围内，就++，要将两个矩形都包住，要+1
        for (int y1 = 0, y2 = 1; y2 < numbers.size(); y2++) {
            while (numbers[y2] - numbers[y1 + 1] + 1 > len) y1++;
            if (sum[x2][y2] - sum[x1][y2] - sum[x2][y1] + sum[x1][y1] >= m)
                return true;
        }
    }
    return false;
}

// 获取离散化之后的坐标
int get(int x) {
    int l = 0, r = numbers.size() - 1;
    while (l < r) {
        int mid = (l + r) >> 1;
        if (numbers[mid] >= x) r = mid;
        else l = mid + 1;
    }
    return r;
}

int main() {
    cin >> m >> n;
    numbers.push_back(0);
    for (int i = 0; i < n; i++) {
        int x, y; cin >> x >> y;
        numbers.push_back(x);
        numbers.push_back(y);
        points[i] = {x, y};
    }
    sort(numbers.begin(), numbers.end());
    numbers.erase(unique(numbers.begin(), numbers.end()), numbers.end());

    // 离散化
    for (int i = 0; i < n; i++) {
        int x = get(points[i].first), y = get(points[i].second);
        sum[x][y]++;
    }

    // 前缀和
    for (int i = 1; i < numbers.size(); i++)
        for (int j = 1; j < numbers.size(); j++)
            sum[i][j] += sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1];

    // 二分找最小边长
    int l = 1, r = 10000;
    while (l < r) {
        int mid = (l + r) >> 1;
        if (check(mid)) r = mid;
        else l = mid + 1;
    }

    cout << r << endl;

    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
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71

9.7 糖果传递

ACwing 122

#include <iostream>
#include <algorithm>
using namespace std;

typedef long long LL;
const int N = 1e6 + 10;

int n;
LL s[N], c[N];

int main() {
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    scanf("%d", &n);
    for (int i = 1; i <= n; i ++ ) {
        int x;
        scanf("%d", &x);
        s[i] = s[i - 1] + x;
    }
    
    LL avg = s[n] / n;
    for (int i = 1; i <= n; i ++ ) c[i] = s[i - 1] - (i - 1) * avg;
    sort(c + 1, c + n + 1);
    
    long long res = 0;
    for (int i = 1; i <= n; i ++ )
        res += abs((long long)c[i] - c[(n + 1) / 2]);
        
    printf("%lld\n", res);
    
    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

9.8 士兵

ACwing 123

首先，一个士兵横着走和竖着走是相互独立的。那么可以先让士兵先竖着走，然后横着走才到最终位置。最终的最小步数即竖着走的最小步数与横着走的最小步数之和。

首先对于纵坐标，要找出一个与$x$轴平行的线，使所有点到该直线距离最小，即取所有点$y$值的中位数。参考 货仓分配 问题。

对于横坐标，首先明确不管是最终移动到的位置与初始位置，任意两个点的相对位置是不会变化的。

证明：假设有两个点$x_1、x_2$且$x_1<x_2$，如果经过移动之后变成$x_2<x_1$，那么移动的距离比$x_1$往右、$x_2$往左，两者移动到$x_1+1=x_2$的位置时的移动距离更大。

假设每个点最初的横坐标为$x_1,x_2,\cdots ,x_n$，最终要移动到的坐标为$a,a+1,\cdots ,a+n-1$的位置。那么每个点移动的距离为 { ∣ x 1 − a ∣ ∣ x 2 − ( a + 1 ) ∣ ⋯ ∣ x n − ( a + n − 1 ) ∣ ⇒ { ∣ x 1 − a ∣ ∣ x 2 − 1 − a ∣ ⋯ ∣ x n − ( n − 1 ) − a ∣

\Rightarrow ⎩⎪⎪⎪⎨⎪⎪⎪⎧​​∣x1​−a∣∣x2​−(a+1)∣⋯∣xn​−(a+n−1)∣​⇒⎩⎪⎪⎪⎨⎪⎪⎪⎧​​∣x1​−a∣∣x2​−1−a∣⋯∣xn​−(n−1)−a∣​令$x_i-(i-1)=b_i$，则有 { ∣ b 1 − a ∣ ∣ b 2 − a ∣ ⋯ ∣ b n − a ∣

⎧⎩⎨⎪⎪⎪⎪⎪⎪|b1−a||b2−a|⋯|bn−a|$$\{\begin{array}{ll}& |b_1-a|\\ & |b_2-a|\\ & \cdots \\ & |b_n-a|\end{array}$$

⎩⎪⎪⎪⎨⎪⎪⎪⎧​​∣b1​−a∣∣b2​−a∣⋯∣bn​−a∣​到这里处理方法同 货仓分配 问题。

#include <iostream>
#include <algorithm>
using namespace std;

const int N = 10010;

int n;
int x[N], y[N];

int work(int *q) {
    sort(q, q + n);
    int res = 0;
    for (int i = 0; i < n; i++) res += abs(q[i] - q[n / 2]);
    return res;
}

int main() {
    cin >> n;
    for (int i = 0; i < n; i++) cin >> x[i] >> y[i];
    sort(x, x + n);
    for (int i = 0; i < n; i++) x[i] -= i;

    cout << work(x) + work(y) << endl;

    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

9.9 数的进制转换

ACwing 124

记输入进制为$a$进制，输出进制为$b$进制。

一般做法：
先将$a$进制转换为$10$进制数，使用秦九韶算法，需要使用高精度，如$$(12345{)}_5\to (((1\times 5+2)\times 5+3)\times 5+4)\times 5+5{)}_{10}$$然后将$10$进制数转换为$b$进制数，使用短除法，如$$(20{)}_{10}\to (202{)}_3$$求解的方法是： x = 20 = 2 × 3 2 + 0 × 3 1 + 2 × 3 0 →   x   %   3 = 20   %   3 = 2 ， x = x / 3 = 6 →   x   %   3 = 6   %   3 = 0 ， x = x / 3 = 2 →   x   %   3 = 2   %   3 = 2 ， x = x / 3 = 0

→ → → ​x=20=2×32+0×31+2×30x % 3=20 % 3=2，x=x/3=6x % 3=6 % 3=0，x=x/3=2x % 3=2 % 3=2，x=x/3=0​

优化做法：
核心思想依然是短除法。如图：

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int main() {
    int T; cin >> T;
    while (T--) {
        int a, b; string line;
        cin >> a >> b >> line;
        vector<int> number;
        for (auto c: line) {
            if (c <= '9') number.push_back(c - '0');
            else if (c <= 'Z') number.push_back(c - 'A' + 10);
            else number.push_back(c - 'a' + 36);
        }
        reverse(number.begin(), number.end()); // number中存储的是从低位到高位，需翻转

        // 类似高精度除法
        vector<int> res;
        while (number.size()) {
            int t = 0;
            for (int i = number.size() - 1; i >= 0; i--) {
                number[i] += t * a;
                t = number[i] % b;
                number[i] /= b;
            }
            res.push_back(t);
            while (number.size() && !number.back()) number.pop_back();
        }
        reverse(res.begin(), res.end());

        string b_line;
        for (auto x: res) {
            if (x <= 9) b_line += char('0' + x);
            else if (x <= 35) b_line += char('A' + x - 10);
            else b_line += char('a' + x - 36);
        }

        cout << a << ' ' << line << endl;
        cout << b << ' ' << b_line << endl;
        cout << endl;
    }
    
    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
46

9.10 耍杂技的牛

ACwing 125

算法思路：

假设第$i$头牛的强壮值为$s_i$，重量为$w_i$，将这$n$头牛按照$w_i+s_i$的顺序从小到大排列，最大的危险系数一定是最小的。

算法正确性证明：
假设最优解，即最大的危险系数的最小值为$ans$，通过算法策略的解为$cnt$。

• 首先必然有$cnt\ge ans$；
• 假设最优解不是按照$w_i+s_i$的大小从小到达排序的，那么它一定存在相邻两头牛使得$w_i+s_i>w_{i+1}+s_{i+1}$，并且交换这两头牛不影响其它所有牛的值。现在如果交换两头牛：
  • 对于第$i$个位置上的牛：
    • 交换前的危险系数$P_i=w_1+w_2+...+w_{i-1}-s_i$
    • 交换后的危险系数为${P_i}^{\prime }=w_1+w_2+...+w_{i-1}-s_{i+1}$；
  • 对于第$i+1$个位置上的牛：
    • 交换前的危险系数为$P_{i+1}=w_1+w_2+...+w_i-s_{i+1}$；
    • 交换后的危险系数为${P_{i+1}}^{\prime }=w_1+w_2+...+w_{i-1}+w_{i+1}-s_i$；
      将这四个数同时$w_1+w_2+...+w_{i-1}$，然后加上$s_i+s_{i+1}$，则有 P i = s i + 1 P i ′ = s i P i + 1 = w i + s i P i + 1 ′ = w i + 1 + s i + 1
      Pi=si+1Pi′=siPi+1=wi+siPi+1′=wi+1+si+1$$\begin{array}{rl}& P_i=s_{i+1}\\ & {P_i}^{\prime }=s_i\\ & P_{i+1}=w_i+s_i\\ & {P_{i+1}}^{\prime }=w_{i+1}+s_{i+1}\end{array}$$
      ​Pi​=si+1​Pi​′=si​Pi+1​=wi​+si​Pi+1​′=wi+1​+si+1​​因为$s_i\ge 1，w_i\ge 1$，则有${P_i}^{\prime }<P_{i+1}$，并且已知${P_{i+1}}^{\prime }<P_{i+1}$，就有$({P_i}^{\prime },{P_{i+1}}^{\prime }{)}_{max}<P_{i+1}\le (P_i,P_{i+1}{)}_{max}$。所以可知，只要存在$w_i+s_i>w_{i+1}+s_{i+1}$，将其交换后，其最大危险系数不会变大，因此有$ans\ge cnt$。

综上，可得$ans=cnt$。

#include <iostream>
#include <algorithm>

#define x first
#define y second

using namespace std;

typedef pair<int, int> PII;

const int N = 50010;

int n;
PII cow[N];

int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        int w, s; scanf("%d%d", &w, &s);
        cow[i] = {w + s, w};
    }
    sort(cow, cow + n);
    int res = -2e9, sum = 0;
    for (int i = 0; i < n; i++) {
        int w = cow[i].y, s = cow[i].x - w;
        res = max(res, sum - s);
        sum += w;
    }
    printf("%d\n", res);
    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

9.11 最大的和

9.12 任务