80分求助

wangweichen666 @ 2022-09-10 12:05:46

#include<bits/stdc++.h>
using namespace std;
int n,p,a[100001],i,x,y,z,l[100001];
int main(){
    cin>>n>>p;
    for(i=1;i<=n;i++){
        cin>>a[i];
    }
    while(p!=0){
        cin>>x>>y>>z;
        for(i=x;i<=y;i++){
            a[i]+=z;
        }
        p--;
    }
    sort(a+1,a+n+1);
    cout<<a[1];
    return 0;
}

by Katz @ 2022-09-10 12:07:44

有没有一种可能，这题的数据要用差分捏？

by AcxxMz @ 2022-09-10 12:09:57

这题要用差分数组吧

by Hiro_Akiba @ 2022-09-10 14:37:51

建议学一下差分

by fuyixiang @ 2023-04-02 21:45:39

暴力代码：

#include<iostream>
#include<algorithm>
using namespace std;
int a[5000010];
int main(){
    int n,p;
    scanf("%d %d",&n,&p);
    for(int i=1;i<=n;i++)scanf("%d",&a[i]);
    while(p--){
        int x,y,z;
        cin>>x>>y>>z;
        for(int i=x;i<=y;i++)a[i]+=z;
    }
    sort(a+1,a+n+1);
    cout<<a[1];
    return 0;
} 

结果显而易见，TLE一个点，喜提80分回家！

所以应该用差分

先给不知道差分的人简单讲一下：

差分，是一种能高效修改区间的算法。核心代码是

d[i]=a[i]-a[i-1]

然后，想要修改区间，只需要在区间的d[l]+=z，d[r]-=z。最后做一遍前缀和（d[i]=d[i-1]+a[i]）就可以了。

差分可以直接把O(nn)的时间复杂度优化成O(n)，十分高效。

所以我用差分重做了一遍，AC！

满分代码（code）:

#include<iostream>
using namespace std;
const int M=5e6+1;
int n,p,minn=1e9;
int a[M],d[M];//注意数据范围n=5*1e6 
int main(){
    cin>>n>>p;//读入 
    for(int i=1;i<=n;i++)
        cin>>a[i];//读入数组a[] 
    for(int i=1;i<=n;i++)
        d[i]=a[i]-a[i-1];//差分 
    while(p--){
        int x,y,z;
        cin>>x>>y>>z;
        d[x]+=z;//区间修改 
        d[y+1]-=z;//区间修改 
    }
    for(int i=1;i<=n;i++){
        a[i]=a[i-1]+d[i];//前缀和 
        if(minn>a[i])minn=a[i];//比较大小 
    }
    cout<<minn;//输出答案 
    return 0;
}