60分tle求调

P2367 语文成绩

lby1109 @ 2024-08-04 16:36:59

#include<bits/stdc++.h>
using namespace std;
int n,p,x,y;
unsigned long long a[5000001],_min=18446744073709551615;
short z;
int main() {
//  freopen(".in","r",stdin);
//  freopen(".out","w",stdout);
    scanf("%d%d",&n,&p);
    for(int i=1;i<=n;i++){
        scanf("%llu",&a[i]);
    }
    for(int i=1;i<=p;i++){
        scanf("%d%d%hd",&x,&y,&z);
        for(int j=x;j<=y;j++){
            a[j]+=z;
        }
    }
    for(int i=1;i<=n;i++){
        if(a[i]<_min){
            _min=a[i];
        }
    }
    printf("%llu",_min);
    return 0;
}

算得上暴力代码吗？

by Dangerise @ 2024-08-04 16:52:11

@lby1109 对于每个询问，你都要遍历一遍a数组，显然复杂度为 O(n^2) ，必定超时

看题解吧

by chasm_pain @ 2024-08-21 15:34:25

#include<bits/stdc++.h>
using namespace std;
long long n,p,r=2000000000,x,y,z,a[5000009],b[5000009],h[5000009];
int main(){
    cin>>n>>p;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    for(int i=1;i<=p;i++){
        cin>>x>>y>>z;
        b[x]+=z;
        b[y+1]-=z;
    }
    for(int i=1;i<=n;i++){
        h[i]=h[i-1]+b[i];
        r=min(r,h[i]+a[i]);
    }
    cout<<r;
}

求关注

|