洛谷题单指南-前缀和差分与离散化-P2367 语文成绩

原题链接：https://www.luogu.com.cn/problem/P2367

题意解读：对于数组s[]，给指定q个区间[x, y]里每个数增加z，计算操作之后最小的数。

解题思路：

1、暴力做法

对于每一个区间[x, y]，枚举给每一个数增加z，然后遍历查找最小值，总体时间复杂度为O(N^2)，不可行。

2、一维差分

对于给指定区间[x, y]中每一个数增加z的操作，可以借助差分数组来优化。

什么是差分？

可以理解为前缀和的逆运算，设s[]是a[]的前缀和数组，那么a[]就是s[]的差分数组

如何计算差分？

也就是已知s[]，要计算a[]，由于s[i] = a[1] + ... + a[i]，s[i - 1] = a[1] + ... + a[i - 1]，因此有

a[i] = s[i] - s[i - 1]

如何给s[]数组区间[x, y]每个数增加z？

第一步：给a[x]增加z，由于s[]是a[]的前缀和，因此从s[x]开始到最后每个数都增加了z

第二步：给a[y + 1]减去z，由于s[]是a[]的前缀和，因此从s[y + 1]开始到最后每个数都恢复之前状态，既不增加z也不减少z

这样一来，就只有s[x] ~ s[y]之间每一个数都增加了z

3、完整流程

第一步：计算差分数组

第二步：针对差分数组进行区间加数操作

第三步：重新计算前缀和数组，统计最小值

100分代码：

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

const int N = 5000006;

int n, p;
int s[N], a[N];

int main()
{
    scanf("%d%d", &n, &p);
    for(int i = 1; i <= n; i++)
    {
        scanf("%d", &s[i]);
        a[i] = s[i] - s[i - 1]; //计算差分数组
    }

    int x, y, z;
    for(int i = 1; i <= p; i++)
    {
        scanf("%d%d%d", &x, &y, &z);
        //给区间[x,y]每个数增加z
        a[x] += z;
        a[y + 1] -= z;
    }
    
    int ans = 1e9;
    for(int i = 1; i <= n; i++)
    {
        s[i] = s[i - 1] + a[i]; //用前缀和还原数组
        ans = min(ans, s[i]);
    }
    cout << ans;
    return 0;
}