算法 差分

普通的差分其实很好理解, 就是将一次区间的加减操作换成了两个点的操作 :

void insert(int l, int r, int c, int b[])
{
    b[l] += c;
    b[r + 1] -= c;
}

假设数组大小为n, 其对时间复杂度的贡献发生在区间操作很多时, 假定操作数为m, 那么差分就可以将时间复杂度O(nm)降到O(n), 一般不可以降到O(1), 因为差分完要强绑定一次前缀和(除非你就是要差分数组).

对于差分的深入理解, 可以把其看作一种积分和求导的过程 :

• 差分数组(b) -> 原数组(a) -> 前缀和数组(s), 你可以把这种过程看作一种积分(从前往后累加).
• 差分数组 <- 原数组 <- 前缀和数组, 你可以把这种过程看作一种求导(从后往前累减).

虽然他们数值不同, 但他们同根同源, 你可以理解为是一种事物的不同观察方式, 每种观察方式都有一些特殊的作用和关联. 在比较基础的算法题中, 一般都是站在差分数值的角度去想如何积分成原数组, 但在一些差分题中也会要求你站在原数组角度去求导成差分数组, 接下来给出例题.

空调 : 给出一个原数组x, 再给出一个目标数组y, 你可以选择x中任意的一段区间加减一, 求x转变为y的最小操作数.

我们可以感觉到这道题确实是在进行大量的区间操作, 和差分脱不了干系, 但是并不是让我们求出原数组的什么, 而是求区间操作的最小操作数, 而差分数组中的每次加减就是一次区间操作, 那么这道题其实是希望我们把原数组求导成差分数组, 用差分数组得到答案.

将题目变形一下会更好理解, 题目要求是x->y的区间操作, 我们可转变为x - y -> 0的区间操作, 就是将两个数组相减, 然后求得到的数组d变为0的操作数, 我们还可以将思路逆转一下, 0 -> d的区间操作也一定等同于他, 就是说我们可以把d看作是一个原数组, 对其求导得到差分数组, 差分数组就是我们要的答案.

#include<iostream>
using namespace std;
const int N = 100010;
int n;
int b[N];

int main()
{
    cin >> n;
    for(int i = 1; i <= n; i ++ ) cin >> b[i]; // 读入x
    for(int i = 1; i <= n; i ++ ) // 读入y直接 x - y
    {
        int x;
        cin >> x;
        b[i] -= x;
    }
    
    for(int i = n + 1; i > 0; i -- ) b[i] -= b[i - 1]; // 求导
    
    // 因为差分数组一定是一加一减, 并且sum(+) + sum(-)一定等于0, 那么操作次数其实就是看正数总和就行
    int sum = 0;
    for(int i = 1; i <= n + 1; i ++ )
        if(b[i] > 0) sum += b[i];
    cout << sum << endl;
    return 0;
}

给定 𝑛 次操作，每次操作会让区间 [𝑠𝑖,𝑡𝑖] 区间减 𝑐𝑖，并且给定 𝑚 次付费操作，其中第 𝑖 个操作可以让区间 [𝑎𝑖,𝑏𝑖] 加上 𝑝𝑖，代价为 𝑚𝑖，求让全集非负的最小代价。

这题就是很正常的思路, 是从差分数组求积分变为原数组的过程, 不过加入了空调, 需要通过dfs得到最小代价.

#include<iostream>
#define rep(i, a, b) for(int i = (a); i <= (b); i++ )
#define int long long
using namespace std;
int n, m;
int p[200]; // 所有牛栏的降温需求
int b[200]; // 枚举的空调的降温
int a[200];
int ans = 0x3f3f3f3f;

struct node{
    int a, b, p, m;  // 范围, 降温, 花销
}nodes[20];

// 空调只有10个枚举用不用就行
void insert(int l, int r, int c, int b[])
{
    b[l] += c;
    b[r + 1] -= c;
}

void dfs(int u, int sum)
{
    if(u > m)
    {
        // 将两个差分数组对比, 符合条件就和ans比较
        rep(i, 1, 100) a[i] = b[i] + a[i - 1];
        rep(i, 1, 100) 
        {
            if(a[i] < p[i] && p[i] != 0) return;
        }
        ans = min(ans, sum);
        return;
    }
    
    // 不选
    dfs(u + 1, sum);
    // 选
    insert(nodes[u].a, nodes[u].b, nodes[u].p, b);
    dfs(u + 1, sum + nodes[u].m);
    insert(nodes[u].a, nodes[u].b, -nodes[u].p, b);
}

signed main()
{
    cin >> n >> m;
    rep(i, 1, n)
    {
        int s, t, c;
        cin >> s >> t >> c;
        insert(s, t, c, p);
    }
    rep(i, 1, 100) p[i] += p[i - 1];
    
    rep(i, 1, m)
    {
        int a, b, p, c;
        cin >> a >> b >> p >> c;
        nodes[i] = {a, b, p, c};
    }
    
    dfs(1, 0);
    cout << ans << endl;
    return 0;
}

给定一个序列 𝑎𝑖，每次操作可以选择一个位置 𝑝，令从 𝑎𝑝 开始的每个数都加上一个以 1 或者 -1 为公差的从 1/-1 开始的等差数列。最小化让序列归零的操作次数。

这题也是让我们求区间操作的次数的, 如果我们做过第一题应该可以很敏锐地察觉到这应该是求导到差分数组, 但是和第一题不一样的是, 我们的区间操作所构成的结果是一个从1开始公差为1等差数列而不是1! 这时我们应当认识到, 是我们的操作做了积分.

假设我们的操作本来就是对一个区间加减一, 现在是差分数组 :

• 1 0 0 0 0 0 (边界)

然后我们对其积分, 变成原数组 :

• 1 1 1 1 1 1 (边界)

我们再对其积分, 变成前缀和数组 :

• 1 2 3 4 5 6 (边界)

我们发现, 只要积分两次, 那么我们普通的差分操作就会变成题目中的等差数列区间操作.

我们的目的是a -> 0, 那么也可以翻转成 0 -> a, 这个过程是通过等差数列区间操作实现的.

那么只要我们把a求导两次, 就可以把这种操作转化成普通的差分操作.

由于本题操作区间一定到最右, 所以右边的边界问题就不用考虑了.

#include <iostream>
#define rep(i, a, b) for(int i = (a); i <= (b); i ++ )
#define int long long
using namespace std;
const int N = 200010;
int n;
int s[N];

signed main()
{
    cin >> n;
    rep(i, 1, n) cin >> s[i];  							// s
    for(int i = n; i >= 1; i -- ) s[i] -= s[i - 1];		// s -> a
    for(int i = n; i >= 1; i -- ) s[i] -= s[i - 1];		// a -> b
    int ans = 0;
    rep(i, 1, n) ans += abs(s[i]); // 正负操作都算
    cout << ans << endl;
    return 0;
}