Test - 1 20260204

Test - 1

A 语文成绩 Luogu P2367

前缀和与差分

题单：第2单元 前缀和与差分

解法1：

暴力的做法就是直接记录每个人的成绩

若对 \([x,y]\) 同学的成绩都加 \(z\)，就枚举 \([x,y]\) 内每个同学，成绩加 \(z\)

最后统计成绩最小值，输出即可

时间复杂度 \(O(np)\)，只能得到 \(60\) 分。

解法2：

看到区间加，可以想到差分，将修改成绩所需 \(O(n)\) 的时间复杂度将为 \(O(1)\)

统计成绩的差分数组 \(d\)，若将 \([x,y]\) 同学的成绩都加 \(z\)，相当于 \(d[x]+z,d[y+1]-z\)

对差分数组求前缀和即为原数组，统计成绩最小值输出即可

时间复杂度 \(O(p)\)，可以 \(\text{AC}\)

scanf("%d%d",&n,&p);
for(int i=1;i<=n;i++)
{
    scanf("%d",&a[i]);
    d[i]=a[i]-a[i-1];
}

for(int i=1;i<=p;i++)
{
    int x,y,z;
    scanf("%d%d%d",&x,&y,&z);
    d[x]+=z; d[y+1]-=z;
}

for(int i=1;i<=n;i++)
{
    a[i]=a[i-1]+d[i];
    ans=min(ans,a[i]);
}
printf("%d\n",ans);

B-E

参考 ABC443 A-D 题解