洛谷 P2367 语文成绩 刷题笔记

P2367 语文成绩 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

差分?

令a[i]为b[i]数组的前缀和

a[n]=b[1]+b[2]+b[3]+.....+b[n];

a[n-1]=b[1]+b[2]+b[3]+.....+b[n-1];

构造差分数组 b[i]=a[i]-a[i-1];

有什么好处 当我们想对a[l]--a[r]范围内所有数据加上一个数x

不必循环 for(int i=l;i<=r;i++) a[i]+=x;

直接

b[l]+=c;//从l-n的范围全部+c;

b[r+1]-=c;//将r+1到n范围多加的C减掉

自此我们快速将一个循环才能完成的操作优化 （主要是为了以后学二维的差分做铺垫）

对于构造差分数组 我们采取 add ()函数?

void add(int l,int r,int x){
?? ?b[l]+=x;
?? ?b[r+1]-=x;
?? ?
}

for(int i=1;i<=n;i++){
?? ??? ?cin>>a[i];
?? ??? ?add(i,i,a[i]);//构造b[i] 差分数组
?? ??? ??
?? ?}

该函数 在首次输入a[i]数组构造差分数组的效果

等价于 b[i]=a[i]-a[i-1]

为什么呢

我们传入了两个i

传进add后?

相当于?

b[i]这个数加上了a[i]

而b[i+1]这个数减去了a[i]

///这一部操作是因为? b[i]=a[i]-a[i-1] 在我们输入下一个a[i]时

//当前的这个a[i]就是下一个a[i]的”a[i-1]"而我们要减去的a[i-1]其实在上一次输入时就已经先减去了

所以读入当前a[i] 只要将b[i](它的值是 -a[i-1] )加上这个a[i]即可?

那我为什么不直接写 b[i]=a[i]-a[i-1] 其实完全没问题?

只是二维差分数组的构造 也采取add 这里先讲了add的原理 以便进一步理解二维差分数组的构造

完整代码

#include<iostream>
using namespace std;
const int N=5e6+10;
int a[N],b[N];
void add(int l,int r,int x){
?? ?b[l]+=x;
?? ?b[r+1]-=x;
?? ?
}
int main(){
?? ?int n,m;
?? ?cin>>n>>m;
?? ?for(int i=1;i<=n;i++){
?? ??? ?cin>>a[i];
?? ??? ?add(i,i,a[i]);//构造b[i] 差分数组

//此处的insert 操作的实际效果?
?? ?//与该语句 ?b[i]=a[i]-a[i-1]; ?相同 ；
?? ? ? ?//初始化 插入差分数组 ?
?? ? ? ?//使b[i]变成当前 ?a[i]的差分数组?
?? ?//b数组为空 将a数组的原始值插入b数组 就是按照差分处理的形式
?? ?//初始化b数组的原始缓存 ?
?? ??? ??
?? ?}
?? ?for(int i=0;i<m;i++){
?? ??? ?int a,b,c;
?? ??? ?cin>>a>>b>>c;
?? ??? ?add(a,b,c);

????????????????//执行增值操作 ?
?? ? ? ?//但是只是对差分数组 ?进行了增值操作 ?
?? ? ? ?//a数组是b数组的前缀和数组?
?? ??? ?//而b数组 就是a数组 未经扫描的冗沉 缓存
?? ??? ?//我们对b数组的操作 只是暂时记录了增减情况 还没把这个情况汇报给a数组

?? ?}

?? ?for(int i=1;i<=n;i++){
?? ??? ?a[i]=a[i-1]+b[i];

? ? ? ? ?//扫描一编操作的增减值?
?? ? ? ?//计算前缀和 ?
? ? ??
?? ?}
?? ?
?? ?int minn=a[1];
?? ?for(int i=1;i<=n;i++){
?? ?
?? ??? ?minn=min(a[i],minn);
?? ?}
?? ?cout<<minn;
?? ?return 0;
}

举个例子模拟一下缓存池情况?

对于以下代码

插入改组数据

?/*
? ?
?? ?6 3
1 2 2 1 2 1
1 3 1
3 5 1
1 6 1*/

#include<iostream>
using namespace std;
const int N=100010;
int a[N],b[N];?? ?int n,m;
void insert(int l,int r,int c){

?? ?b[l]+=c;
?? ?//b[l]到n的位置加上 ?c?
?? ?b[r+1]-=c;
?? ?//减去 上一步中多加的【r+1】到n的部分
?? ?cout<<"当前缓存池 is ?";
?? ?for(int i=1;i<=n;i++){
?? ??? ?cout<<b[i]<<' ';
?? ?}
?? ?cout<<endl;
?? ?}
int main(){

?? ?cin>>n>>m;

?? ?for(int i=1;i<=n;i++){
?? ? ? ?cin>>a[i];
?? ?}

?? ?for(int i=1;i<=n;i++){
?? ? ? ?insert(i,i,a[i]);
?? ?//此处的insert 操作的实际效果?
?? ?//与该语句 ?b[i]=a[i]-a[i-1]; ?相同 ；
?? ? ? ?//初始化 插入差分数组 ?
?? ? ? ?//使b[i]变成当前 ?a[i]的差分数组?
?? ?//b数组为空 将a数组的原始值插入b数组 就是按照差分处理的形式
?? ?//初始化b数组的原始缓存 ?
?? ?}
?? ?
? ?
?? ?while(m--){
?? ?
?? ? ? ?int l,r,c;
?? ? ? ?cin>>l>>r>>c;
?? ? ? ?insert (l,r,c);
?? ? ? ?//执行增值操作 ?
?? ? ? ?//但是只是对差分数组 ?进行了增值操作 ?
?? ? ? ?//a数组是b数组的前缀和数组?
?? ??? ?//而b数组 就是a数组 未经扫描的冗沉 缓存
?? ??? ?//我们对b数组的操作 只是暂时记录了增减情况 还没把这个情况汇报给a数组?
?? ??? ??
?? ?}
?? ?for(int i=1;i<=n;i++){
?? ?
?? ? ? ?a[i]=a[i-1]+b[i];
?? ? ? ?//扫描一编操作的增减值?
?? ? ? ?//计算前缀和 ?
?? ?}
?? ?for(int i=1;i<=n;i++){
?? ?
?? ? ? ?//cout<<a[i]<<' ';
?? ?}
?? ?return 0;
}

缓存池情况