80分#2wa!求助犇犇%>_<%

P2367 语文成绩

wzhbsm @ 2024-09-23 10:51:18

#include<bits/stdc++.h>
using namespace std;
int n,p,a[5000005],b[5000005],x,y,z;

int main()
{
    scanf("%i%i",&n,&p);
    for(int i=1;i<=n;i++)
    {
        scanf("%i",&a[i]);
        b[i]=a[i]-a[i-1];
    }
    for(int i=1;i<=p;i++)
    {
        scanf("%i%i%i",&x,&y,&z);
        b[x]+=z;
        b[y]+=z;
    }
    int m=1000;
    for(int i=1;i<=n;i++)
    {
        a[i]=a[i-1]+b[i];
        if(m>a[i]) m=a[i];
    }
    printf("%i",m);
    return 0;
}

为什么18行必须是b[y]-=z;??!


by 20111019Yu @ 2024-09-23 11:50:56

因为差分数组的元素是原数组元素的差。

元素组上有一段增加 x。比如 a_{i}~a_{j}

那么因为 b_{i}=a_{i}-a_{i-1},所以 b_{i} 增加了x。

$b_{j+1}=a_{j+1}-a_{j}$,所以 $b_{j+1}$ 应减 $x$。

|