AcWing100 增减序列（差分）

2021-03-03 06:27

阅读：733

标签：ons main scan long gif 数组 class bsp typedef

看到区间修改，可以想想差分，这题显然就是在差分数组后，将b1-bn变为0，而个数就是b1的个数

最优答案肯定是刚开始挑一个正的和一个负的消掉，当某一个数被消完后，后面的就是跳同一种操作。

那么个数就是正数-负数的绝对值+1

#includeusing namespace std;
typedef long long ll;
const int N=3e5+10;
int a[N],b[N];
int main(){
    int i;
    int n;
    cin>>n;
    ll cnt1=0;
    ll cnt2=0;
    for(i=1;i){
        scanf("%d",&a[i]);
        b[i]=a[i]-a[i-1];
        
    }
    for(i=2;i){
        if(b[i]>0)
            cnt1+=b[i];
        if(b[i]0)
            cnt2-=b[i];
    }
    coutendl;
    cout1endl;
}

View Code

AcWing100 增减序列（差分）

标签：ons main scan long gif 数组 class bsp typedef

原文地址：https://www.cnblogs.com/ctyakwf/p/12989843.html

上一篇：history api 与 hashchange

下一篇：[Win32]事件

文章来自：搜素材网的编程语言模块，转载请注明文章出处。
文章标题：AcWing100 增减序列（差分）
文章链接：http://soscw.com/index.php/essay/59397.html

亲，登录后才可以留言！

AcWing100 增减序列（差分）

评论

热门文章

推荐文章

最新文章

置顶文章