求助，最后两个一直超时

1145141919810HOMO11 @ 2023-08-01 09:44:06

by Alg_orithm @ 2023-08-01 09:59:55

https://www.luogu.com.cn/record/118370601

by 1145141919810HOMO11 @ 2023-08-01 10:02:29

@GeorgeFan 大牛，求帮

by yzm0325 @ 2023-08-01 10:02:50

@1145141919810HOMO11 就是差分啊

by Alg_orithm @ 2023-08-01 10:08:35

@1145141919810HOMO11 我来说差分不好说，你看一下题解的第1篇，那篇写得好,不行的话再用表格模拟一下

by Alg_orithm @ 2023-08-01 10:09:16

思路 这题明显就是差分 根据差分数组的定义： d[i]=a[i]-a[i-1]，可以发现，在d[x]上加上z,会让后面的学生全部加上z。 但这是把后面全部都加了，还要减掉一节，所以 把两个综合起来就是 所以每一次变化只要把d[x]+z,d[y+1]-z就好了。 因为 d[i]=a[i]-a[i-1] 所以 a[i-1]+d[i]=a[i] 最后再根据 a[i-1]+d[i]=a[i]输出每一个同学的分数 代码

#include<bits/stdc++.h>
using namespace std;
int d[5000001];//d[i]表示a[i]-a[i-1] 
int a[5000001];
int main()
{
    int n,p,x,y,z,i,min=1e9;
    cin>>n>>p;
    for(i=1;i<=n;i++)
    {
        cin>>a[i];
    }

    for(i=1;i<=n;i++)
    {
        d[i]=a[i]-a[i-1];
    }
    for(i=0;i<p;i++)
    {
        cin>>x>>y>>z;
        d[x]+=z;
        d[y+1]-=z;
    }

    for(i=1;i<=n;i++)
    {
        a[i]=a[i-1]+d[i];
        if(min>a[i])
        {
            min=a[i];
        }
    }
    cout<<min;
    return 0;
} 

by Alg_orithm @ 2023-08-01 10:09:36

复制题解

by Wangqinshu @ 2023-08-11 13:58:14

正解是差分，枚举肯定会超时啊。