?今天學了 差分********* ? ? 很明白 ? ? 然后 配合著luogu上的題寫一下吧 ? 裸的差分 ? 當時一直打暴力60分 ?交了十幾次 ?今天才知道 ?查詢修改什么的是差分
?
直接看題把
?
輸入輸出格式輸入格式：
第一行有兩個整數n，p，代表學生數與增加分數的次數。第二行有n個數，a1~an，代表各個學生的初始成績。接下來p行，每行有三個數，x，y，z，代表給第x個到第y個學生每人增加z分。輸出格式：
輸出僅一行，代表更改分數后，全班的最低分。
根據zhw老師說的 ?先定義一個b數組 ?用來 加速
就像 ? ?b[i]=a[i]-a[i-1]
搞到最后 ?就等價于 ??
a[i]=b[i]+.......b[1]
操作的話 只需要在b[x]+z ? b[y+1]-z ?就好 ?加速嘛
?
代碼：
?
#include<iostream> #include<cstdio> using namespace std; int n,p,x,y,z,a[5000010],b[5000010],ans,sum=1111111; int main() {scanf("%d%d",&n,&p);for(int i=1;i<=n;i++){scanf("%d",&a[i]);b[i]=a[i]-a[i-1]; }for(int i=1;i<=p;i++){scanf("%d%d%d",&x,&y,&z);b[x]+=z;b[y+1]-=z;}for(int i=1;i<=n;i++){ans+=b[i];sum=min(sum,ans);}printf("%d",sum); }
?
?
?
?
?
)
