用的差分和sort，为啥最后一个点TLE了

Apple3 @ 2024-02-22 20:32:31

#include <bits/stdc++.h>
using namespace std;

const int N=5e6+10;
long long g[N],d[N];
long long ans; 

int main(){
    int n;cin>>n;
    int p;cin>>p;

    for(int i=1;i<=n;i++) cin>>g[i];
    for(int i=1;i<=n;i++) d[i]=g[i]-g[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++) g[i]=g[i-1]+d[i];
    sort(g+1,g+1+n);
    cout<<g[1];         
    return 0;
} 

by lunjiahao @ 2024-02-22 20:36:55

@Apple3

数据范围 1 \leq n \leq 5 \times 10^6 ，要用 scanf 读入。

by xd244 @ 2024-02-22 20:38:38

@Apple3 我用cin也AC了.

#include<iostream>
using namespace std;
int main(){
    int n,m,l,r,p,a[5000010]={},cf[5000010]={},s[5000010]={},minn=1e9;cin>>n>>m;
    for(int c=1;c<=n;c++){
        cin>>a[c];
        cf[c]=a[c]-a[c-1];
    }for(int c=1;c<=m;c++){
        cin>>l>>r>>p;
        cf[l]+=p;
        cf[r+1]-=p;
    }for(int c=1;c<=n;c++){
        s[c]=s[c-1]+cf[c];
        minn=min(minn,s[c]);
    }cout<<minn;
}

by Apple3 @ 2024-02-22 20:39:52

@lunjiahao 但把sort换成遍历数组求最小就过了，这是为啥啊

by lunjiahao @ 2024-02-22 20:41:47

@Apple3

sort的时间复杂度为 O(n\log n)，而遍历找最小值的复杂度为 O(n)，这里既然你只是找最小值求没必要sort直接遍历

by lunjiahao @ 2024-02-22 20:43:40

因为你前面读入约 10^7 的数据没用scanf，侥幸卡过测评但也会接近超时，再加上sort的 O(n \log n) 妥妥超时了啊。

by Apple3 @ 2024-02-22 20:45:40

@lunjiahao 所以一般1e6的数据就用scanf读入吗，最好别用cin?

by SMall_X_ @ 2024-02-22 20:47:48

@Apple3 也可以用关闭输入输出流的同步或快读

by lunjiahao @ 2024-02-22 20:48:16

@Apple3

嗯，因为用cin所耗时间较大

但本题主要还有sort的复杂度 O(n \log n)，大有可能这单个sort就会超时了（这题的 n 接近 10^7）

by Apple3 @ 2024-02-22 20:49:56

@lunjiahao 明白了，感谢感谢