当前位置：首页 > article >正文

蓝桥杯每日一题----一维差分

article 2025/3/23 10:17:12

🌈个人主页：羽晨同学

💫个人格言:“成为自己未来的主人~”

题目链接

【模板】差分https://ac.nowcoder.com/acm/problem/226303

解题思路

对于这个一维差分来说，主要是为了解决这种从l到r每个都加上或者减去一个数字的情况。比如说，在我们这道题当中，我们可以看到的是，

所以，当我们使用暴力模拟的时候，时间复杂度是肯定会超过要求的，所以，这个时候，最适合我们的就是进行一维差分。

所谓的差分，就是我们创建一个差分数组，然后存放每个元素和前面一个元素的差值，所以，当我们从L，到R中每个元素都+K的时候，那么差分数字的L就会+K，然后R+1就会-K，其余保持不变。

最后，在复原初始数组的时候，我们可以让原数组+差分数组+原数组的前面一个位置。

下面，我们结合代码来详细说明一下：

首先我们定义差分数组

typedef long long LL;
const int N =1e6+10;
LL a[N];
LL f[N];//差分数组

对差分数组进行初始化

    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        f[i]=a[i]-a[i-1];
    }

然后，对差分数组进行操作

    while(m--)
    {
        int l,r,k;cin>>l>>r>>k;
        f[l]+=k;f[r+1]-=k;
    }

然后进行复原

    for(int i=1;i<=n;i++)
    {
        a[i]=f[i]+a[i-1];
        cout<<a[i]<<" ";
    }

完整代码

#include <iostream>
using namespace std;
typedef long long LL;
const int N =1e6+10;
LL a[N];
LL f[N];//差分数据
int main()
{
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        f[i]=a[i]-a[i-1];
    }
    while(m--)
    {
        int l,r,k;cin>>l>>r>>k;
        f[l]+=k;f[r+1]-=k;
    }
    for(int i=1;i<=n;i++)
    {
        a[i]=f[i]+a[i-1];
        cout<<a[i]<<" ";
    }

    return 0;
}

好了，今天的内容就到这里，我们明天再见。