2023.02.15.差分

标签：15 数字 temp int 2023.02 cin 差分 数组

什么是差分

首先有一个数组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题库

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

 

 

#include<iostream>
using 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]<temp && a[i]>0){
                   for(int j=temp;j>temp-a[i];j--){
                       v[j]=1;
                   }
               }
           }
            temp++;
        }
        for(int s=1;s<=n;s++){
            cout<<v[s]<<" ";
        }
        cout<<endl;
        t--;
    }
    return 0;
}

 下面给出使用差分的做法

在题目中了解到，只要是对数组中的数字有操作就为1，没操作就为0

然后有关于区间的部分，在这里可以使用差分，对新数组中的数字加1，之后判断数组中的数字，如果大于0就置1，否则置0

#include<iostream>
using 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<<endl;
        t--;
    }
    return 0;
}

 

标签：15,数字,temp,int,2023.02,cin,差分,数组
From： https://www.cnblogs.com/hualuoyumufeng/p/17124494.html