算法基础算法

差分的应用

字数统计: 1.6k字   |   阅读时长: 7分

摘要: 差分的应用

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

在文章 【模板】前缀和与差分 中，我们介绍了前缀和与差分的算法思想和代码模板。并在文章 前缀和问题分类汇总 中分类罗列了 leetcode 中的前缀和的题目列表。

差分与前缀和是一对互逆运算，对于一个数列 A[0..n-1]，它的差分数列 B[0..n-1] 定义为：

差分数列的前缀和数列就是原数列 A。将 A[l..r] 都加 1，对应到差分数列 B 上，就是将 B[l] 加 d、B[r + 1] 减 d，其它位置不变，这样就将区间操作转化为差分数列上的但带你操作。在文章 差分维护区间加法 中，我们以两个 leetcode 的题目介绍了差分的这种最基础的应用：维护区间加法。

在文章 LCA,树上倍增,树上差分 中，我们将差分的思想在树上的应用。

本文我们看两个在数列上灵活应用差分的问题。

问题1

给定一个长度为 n 的数列 a1, a2, …, an，每次可以选择一个区间 [l,r]，使下标在这个区间内的数都加一或者都减一。

求至少需要多少次操作才能使数列中的所有数都一样，并求出在保证最少次数的前提下，最终得到的数列可能有多少种。

1
2
3
4
5
6
7
8
9
10
11
输入格式
第一行输入正整数 n。
接下来 n 行，每行输入一个整数，第 i+1 行的整数代表 ai。

输出格式
第一行输出最少操作次数。
第二行输出最终能得到多少种结果。

数据范围
0<n<=1e5,
0<=ai<2147483648

输入样例：
4
1
1
2
2
输出样例：
1
2

算法: 差分

首先求出 a[0..n-1] 的差分序列 b[0..n-1]，其中 b[0] = a[0], b[i] = a[i] - a[i - 1]。假想一个 b[n] 也有一个值 0。

对 a 的每次操作，相当于从 b[0..n] 中任选两个值 b[i], b[j]，其中一个加 1，另一个减 1。目标是把 b[1..n-1] 变为零。最终的 a 就是由 n 个 b[0] 组成的。

选出的 b[i], b[j] 有以下四中情况

  1. 0 < i, j < n, 这种操作会改变 b[1..n-1] 中的两个值，在保证 b[i], b[j] 一正一负的情况下，尽量选这种情况。
  2. i = 0, 0 < j < n，改变 b[1..n-1] 中的一个值，且会改变 b[0]。
  3. 0 < i < n, j = n，改变 b[1..n-1] 中的一个值，不会改变 b[0]。
  4. i = 0, j = n，无意义，因为不改变 b[1..n-1]。

综上，先找出 B 中的正数总和 n1，再找出 B 中的负数的相反数总和 n2，尽量执行 1 类操作，共 min(n1, n2) 次，然后需要执行 abs(n1 - n2) 次 2 类或 3 类操作，可以产生 abs(n1 - n2) + 1 种 b[0]。

总的操作数为 max(n1, n2)，最终数列有 abs(n1 - n2) + 1 种。

代码(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
#include <iostream>
#include <cmath>
#include <vector>

using namespace std;

using ll = long long;

const int N = 1e5 + 5;
ll B[N];

int main()
{
    int n;
    cin >> n;
    ll prev = 0;
    for(int i = 0; i < n; ++i)
    {
        ll cur;
        cin >> cur;
        B[i] = cur - prev;
        prev = cur;
    }
    ll n1 = 0; // 正值之和
    ll n2 = 0; // 负值的相反数之和
    for(int i = 1; i < n; ++i)
    {
        if(B[i] > 0)
            n1 += B[i];
        if(B[i] < 0)
            n2 -= B[i];
    }
    ll net = abs(n1 - n2); // 净值
    cout << max(n1, n2) << endl;
    cout << net + 1 << endl;
}

问题2

有 N 头牛站成一行，被编队为 1、2、3…N，每头牛的身高都为整数。

当且仅当两头牛中间的牛身高都比它们矮时，两头牛方可看到对方。

现在，我们只知道其中最高的牛是第 P 头，它的身高是 H ，剩余牛的身高未知。

但是，我们还知道这群牛之中存在着 M 对关系，每对关系都指明了某两头牛 A 和 B 可以相互看见。

求每头牛的身高的最大可能值是多少。

1
2
3
4
5
6
7
8
9
10
11
12
13
输入格式
第一行输入整数 N,P,H,M，数据用空格隔开。
接下来 M 行，每行输出两个整数 A 和 B ，代表牛 A 和牛 B 可以相互看见，数据用空格隔开。

输出格式
一共输出 N 行数据，每行输出一个整数。
第 i 行输出的整数代表第 i 头牛可能的最大身高。

数据范围
1<=N<=10000,
1<=H<=1000000,
1<=A,B<=10000,
0<=M<=10000

算法: 差分

首先初始化答案 result[0..N-1]，将 N 头牛的身高都设为 H，然后枚举 M 组互相看见的关系，每一组关系都会对某些位置牛产生限制，这些位置的牛的身高就要往下降，直至所有关系都满足之后，所有的牛就都是可能的最大身高了。

对于一组关系 (i, j)，如果 i + 1 = j，则这组关系不会对任意位置的牛有影响。如果 i + 1 < j，那么 result[i+1..j-1] 都减去 1，意思是 result[i+1..j-1] 至少要比 result[i], result[j] 小 1。

这里的对 result[i+1..j-1] 减 1 的操作可以用差分数组 B 维护。B[i+1] 减 1，B[j] 加 1。

M 组关系枚举完后，result 就是 B 的前缀和。

代码(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
#include <iostream>
#include <unordered_set>

using namespace std;

const int MAX_N = 1e4 + 5;
int B[MAX_N];

int key(int i, int j)
{
    return i * MAX_N + j;
}

int main()
{
    int N, P, H, M;
    cin >> N >> P >> H >> M;
    // 初始时 [1..N] 均为 H
    B[1] = H;
    unordered_set<int> setting;
    for(int m = 0; m < M; ++m)
    {
        int a, b;
        cin >> a >> b;
        int i = min(a, b);
        int j = max(a, b);
        if(setting.count(key(i, j)) > 0)
            continue;
        // 区间 [i+1, j-1] 减 1
        B[i + 1] -= 1;
        B[j] += 1;
        setting.insert(key(i, j));
    }
    int pre_sum = 0;
    for(int i = 1; i <= N; ++i)
    {
        pre_sum += B[i];
        cout << pre_sum << endl;
    }
}
Share