【差分+操作】C. Helping the Nature

我不是女神ヾ 2024-03-22 17:15 25阅读 0赞

[Problem - 1700C - Codeforces][]

题意：

![094732f13579406dbcc63647bbdc955b.png][]

思路：

一开始手玩了一下

如果不是高低高的形式，那么一定不能通过操作3把全部元素变成0

因此就是先把所有元素变成高低高的形式

但是低在什么地方不确定

因此考虑枚举中间低谷位置，O(1)计算贡献

但是不是这么想的

对于区间操作，可以考虑差分数组

把区间操作转化为单点操作

操作1：-1 +1

操作2： -1

操作3：+1

目的就是把差分数组全部变成0

先把2~N部分变成0

如果d\[i\]大于0，就考虑操作2

否则考虑操作1，但是操作1会改变d1

因此还需操作3把d1加回去

Code：

#include <bits/stdc++.h>
    
    #define int long long
    #define max(a,b) (a>b?a:b)
    #define min(a,b) (a<b?a:b)
    
    using i64 = long long;
    
    using namespace std;
    
    const int mxn=2e5+10;
    const int mxe=3e5+10;
    const int mod=1e9+7;
    
    int N;
    int a[mxn],d[mxn];
    
    void solve(){
    	cin>>N;
    	for(int i=1;i<=N;i++) cin>>a[i],d[i]=a[i]-a[i-1];
    	int ans=0,t=0;
    	for(int i=2;i<=N;i++){
    		if(d[i]<0) t-=d[i];
    		else ans+=d[i];
    	}
    	ans+=t;
    	if(t<d[1]) ans+=(d[1]-t);
    	else ans+=(t-d[1]);
    	cout<<ans<<'\n';
    }
    signed main(){
        ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
        int __=1;cin>>__;
        while(__--)solve();return 0;
    }

[Problem - 1700C - Codeforces]: https://codeforces.com/problemset/problem/1700/C
[094732f13579406dbcc63647bbdc955b.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/18/5056d77c90534f9e94d63b623689d74b.png

发表评论取消回复

表情：

评论列表（有 0 条评论，25人围观）

还没有评论，来说两句吧...

相关阅读

相关【差分+操作】C. Helping the Nature

[Problem - 1700C - Codeforces][] 题意： ![094732f13579406dbcc63647bbdc955b.png][] 思路：一

我不是女神ヾ/ 2024年03月22日 17:15/ 0 赞/ 26 阅读

相关 c++前缀和与差分

一、前缀和 1、简介前缀和也是一个在比赛中比较实用的方法，他能很快得求出一个区间的和，速度为O(1)。一维的前缀和数组sum\[ i \]就是存的是前i个数的

本是古典何须时尚/ 2023年02月15日 01:14/ 0 赞/ 23 阅读

相关 AcWing 797 差分一维差分 c/c++实现

原题链接：[AcWing 797 差分][AcWing 797] > 题目描述：给出 n 个整数和 m 个操作，每个操作输入三个数 l、r、v，表示将区间 \[l,r\] 中

你的名字/ 2022年12月22日 04:38/ 0 赞/ 204 阅读

相关 Healing Psoriasis The Natural Alternative-PREFACE

A New Beginning When a thing is understood, the cure is half accomplished. —Ann

偏执的太偏执、/ 2022年09月12日 10:49/ 0 赞/ 17 阅读

相关 Healing Psoriasis The Natural Alternative-Psoriasis: Psoriasis: The “Inside” Story

Psoriasis: The “Inside” Story Doctor, you must help me—I can no longer go on living th

小灰灰/ 2022年09月12日 10:49/ 0 赞/ 36 阅读

相关差分差分差分

class Solution { public: / 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可返回m天后

我不是女神ヾ/ 2022年08月31日 02:15/ 0 赞/ 299 阅读

相关 Lisp的本质（The Nature of Lisp）

中文网址：http://www.csdn.net/article/2012-11-22/2812113-The-Nature-Of-Lisp 英文原文网址：http://ww

Love The Way You Lie/ 2022年08月25日 15:47/ 0 赞/ 295 阅读

相关差分约束系统C++实现

差分约束：线性规划矩阵A的每一行包含一个1与一个-1，其他元素为0.因此，由Ax<=b给出的约束条件是m个差分约束集合，其中包含n个未知元。每个约束条件为不等式： xj-x

怼烎@/ 2022年06月18日 12:43/ 0 赞/ 221 阅读

相关差分约束系统C++实现

差分约束：线性规划矩阵A的每一行包含一个1与一个-1，其他元素为0.因此，由Ax<=b给出的约束条件是m个差分约束集合，其中包含n个未知元。每个约束条件为不等式： xj-x

雨点打透心脏的1/2处/ 2022年05月15日 13:22/ 0 赞/ 251 阅读

相关差分

概念对于一个数组a\[n\]，有m次操作，都是对区间\[l,r\]加上k，完事后输出数组在知道第一个数a\[1\]的情况下，如果我们知道后面的数与前一个数的差值p，

我不是女神ヾ/ 2021年11月01日 10:04/ 0 赞/ 381 阅读