暴力为什么60分

SOCIQWQ @ 2023-02-02 12:39:13

#include<bits/stdc++.h>
using namespace std;
int main(){
    int n,p,a[10000] = {0},x,y,z,minn = 100000000;
    scanf("%d %d",&n,&p);
    for(int i = 0;i < n;i++) scanf("%d",&a[i]);
    for(int i = 0;i < p;i++){
        scanf("%d %d %d",&x,&y,&z);
        for(int i = x - 1;i < y;i++) a[i] += z;
    }
    for(int i = 0;i < n;i++) if(a[i] <= minn) minn = a[i];
    printf("%d",minn);
    return 0;
}

by Micnation_AFO @ 2023-02-02 12:41:26

有 UB 吧

by Accelessar @ 2023-02-02 13:09:27

数组开小了。但是你开大点也是后两点 TLE

by ceert @ 2023-02-02 19:04:48

数组开小了。但是开大就tle了，建议用差分

by FJ_OIer @ 2023-02-06 19:28:25

@SOCIQWQ

数组开小了，但是开大了就T了，此题正解是差分。

by yzm0325 @ 2023-02-11 17:55:40

差分

by liuhaoxuan247 @ 2023-03-06 20:57:01

此题正解是差分

by fuyixiang @ 2023-03-18 21:03:48

@SOCIQWQ

第一个问题就是数组开小了（当然，这不是问题的关键，就算开大了还是TLE。）。

最关键的问题在于时间复杂度，最重要部分（区间修改）的时间复杂度为O(n*n)，应该用差分，时间复杂度为O(n).

by Wangqinshu @ 2023-08-11 14:00:54

数组开小了，正解是差分，枚举会超时。