最新要闻

广告

手机

iphone11大小尺寸是多少？苹果iPhone11和iPhone13的区别是什么？

iphone11大小尺寸是多少？苹果iPhone11和iPhone13的区别是什么？

 警方通报辅警执法直播中被撞飞：犯罪嫌疑人已投案

警方通报辅警执法直播中被撞飞：犯罪嫌疑人已投案

家电

  1. 首页
  2. 移动通信
  3. 内容

今日热文：2023.02.15.差分

来源：博客园

什么是差分

首先有一个数组a，在里面包含数据


【资料图】

我们定义一个数组b，使每个元素有一下规则 b[i] = a[i] -a[i-1](a从一开始保存数据，a[0] = 0)

也就是说，a数组是b数组的前缀和数组，反过来我们把b数组叫做a数组的差分数组。换句话说，每一个a[i]都是b数组中从头开始的一段区间和。

a[1] = b[1]

a[2] = b[1] +b[2]

a[3] = b[1] +b[2] + b[3]

"

"

"

规律如上

对于差分，我们在使用时，比如某个区间都要加上a（a代表任意数字）使用差分就更简便

公式如下，设区间的左右边界为l和r，这时,b[l] += a;b[r+1] -= c;

例题如下

3729. 改变数组元素 - AcWing题库

在这里我首先使用的算法是贪心遍历，超时了

#includeusing namespace std;int main(){    int t;    cin>>t;    int n;    int a[100]; // 存储原始数字    int v[100]={0}; //用于保存心得数字    int temp = 1; //在这里保存数组个数    while(t>0){ //多次输入        cin>>n;        for(int i=1;i<=n;i++){            cin>>a[i]; //输入数字            v[i]=0; 初始化为0        }        for(int i=1;i<=n;i++){            v[temp]=0; //第一步操作在数组末尾添加0           if(a[i]!=0){ //开始进行第二步操作 进行判断               if(a[i]>=i){                   for(int j=1;j<=temp;j++){                       v[j]=1;                   }               }else if(a[i]0){                   for(int j=temp;j>temp-a[i];j--){                       v[j]=1;                   }               }           }            temp++;        }        for(int s=1;s<=n;s++){            cout<
下面给出使用差分的做法
在题目中了解到，只要是对数组中的数字有操作就为1，没操作就为0
然后有关于区间的部分，在这里可以使用差分，对新数组中的数字加1，之后判断数组中的数字，如果大于0就置1，否则置0
#includeusing namespace std;int main(){    int t;    cin>>t;    int n;    int v[200005]={0};    int a[200005]={0};    while(t>0){        cin>>n;        for(int i=1;i<=n;i++){            v[i]=0;            cin>>a[i];        }        for(int i=1;i<=n;i++){            int x=min(a[i],i); //使用差分进行区间的加法            v[i-x+1]++;            v[i+1]--;        }        for(int i=1;i<=n;i++){            v[i]+=v[i-1];//输出差分数组        }        for(int i=1;i<=n;i++){            if(v[i]>=1){                cout<<1<<" ";            }else{                cout<<0<<" ";            }            v[i]=0;        }        cout<                 

关键词：         
       也就是说 
              
       可以使用