这题能用暴力吗？

没见过AC @ 2021-11-27 08:37:31

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

by 没见过AC @ 2021-11-27 08:38:35

如果不行我就用差分了

by cyffff @ 2021-11-27 08:44:23

为什么能用暴力

by ieeqwq @ 2021-11-27 08:44:44

你算算时间复杂度呢。。

by 普通的壹佰 @ 2021-11-27 08:59:32

这不是线段树吗

by _l_l_l_l_l_ @ 2021-11-27 09:23:32

@普通的壹佰 其实差分就能水过去

by lym12321 @ 2021-11-27 10:24:49

这不就是差分吗

by 无咕_ @ 2021-11-27 22:53:49

@没见过AC

• 显然不能，n,p\le 5\times 10^6，用暴力极限复杂度 \Theta(np)，显然不行

• 建议最值初始值用类型上限，如int上限用2147483647或-2147483648，毕竟出题人是及其阴险的

• 此题非正解：线段树，时间复杂度 \Theta(\log_2^np)；差分，时间复杂度 \Theta(p)

by 无咕_ @ 2021-11-27 23:21:40

@没见过AC 差分解法：

#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
const int MAXN=5e6+9;
long long a[MAXN]; 
long long n,p,minn=6e18;
int main(){
    scanf("%lld %lld",&n,&p);
    for(int i=1;i<=n;i++)scanf("%lld",&a[i]);
    for(int i=n;i>=1;i--)a[i]-=a[i-1];
    for(int i=1;i<=p;i++){
        long long x,y,w;
        scanf("%lld %lld %lld",&x,&y,&w);
        a[x]+=w;
        if(y+1<=n)a[y+1]-=w;
    }minn=min(a[1],minn);
    for(int i=2;i<=n;i++){
        a[i]+=a[i-1];
        minn=min(a[i],minn);
    }printf("%lld\n",minn);
    return 0;
}

ps:撸了二十分钟左右，最后发现数据范围（格局）小了

by 无咕_ @ 2021-11-27 23:24:19

@无咕_ 我这里long long上限因为懒就写了6e18，这个题介绍里保证不超过int的，只是因为习惯我才long long。。。