60分求助!!!c++

libohan356218 @ 2024-04-20 09:23:54

#include <bits/stdc++.h>
using namespace std;
int const N = 1e6+10;
int n,m,a[N],b[N];
void tt(int l,int r,int c){
    b[l]+=c;
    b[r+1]-=c;
}
int main(){
    cin>>n>>m;
    for(int i = 1;i<=n;i++){
        cin>>a[i];
        tt(i,i,a[i]);
    }
    while(m--){
        int l,r,c;
        cin>>l>>r>>c;
        tt(l,r,c);
    }
    for(int i = 1;i<=n;i++){
        b[i]+=b[i-1];
    }
    sort(b,b+n);
    cout<<b[1];
    return 0;
}

by appear_hope @ 2024-04-20 09:55:50

错误点：

1. 没读题 n 有 5 \times 10^6 级别。

2. 请问你会用 sort 吗？

优化点：

1. 如果你用 sort 会 TLE，请问你知道 n \times \log_{2} n 会有多大吗？你为什么不直接求 min 值呢？

这是帮你该处的 AC 代码：

#include <bits/stdc++.h>

using namespace std;

int const N = 5e6 + 10;

int n, m, ans = INT_MAX, a[N], b[N];

void tt(int l, int r, int c){
    b[l] += c, b[r + 1] -= c;
}

int main(){
    cin >> n >> m;
    for(int i = 1; i <= n; i++){
        cin >> a[i];
        tt(i, i, a[i]);
    }
    for(int l, r, c; m--; ){
        cin >> l >> r >> c;
        tt(l, r, c);
    }
    for(int i = 1; i <= n; i++){
        b[i] += b[i - 1];
        ans = min(ans, b[i]);
    }
    cout << ans;
    return 0;
}

by libohan356218 @ 2024-04-20 10:46:42

@appear_hope 谢谢

by appear_hope @ 2024-04-20 23:13:08

不用谢