当前位置:网站首页>1700C - Helping the Nature
1700C - Helping the Nature
2022-07-06 10:01:00 【Stellaris_L】
题目
题意
给一个数组,存在以下三种操作,
- (1)将数组中 a 1 ∼ a i a_1\sim a_i a1∼ai 的数减一。
- (2)将数组中 a i ∼ a n a_i\sim a_n ai∼an 的数减一。
- (3)将数组中全部数加一。
求将数组全部数字变为 0 的最小操作数。
使用差分数组,将原数组变为全零转化为将差分数组变为全零。可以将原来的操作进行转化。
- (1) b 1 − 1 b_1-1 b1−1, b i + 1 b_i+1 bi+1。
- (2) b i − 1 b_i-1 bi−1。
- (3) b 1 + 1 b_1+1 b1+1。
所以,发现只有操作(1)能对除 1 以外的数字加一,只有操作(2)能对除 1 以外位置减一,所以只需要对差分数组除 1 以外的位置进行处理,最后用(2)(3)操作判断位置 1 就可以。
注意要开 long long。
#include <iostream>
using namespace std;
typedef long long ll;
const int N=2e5+10;
ll T,a[N],b[N];
void slove(){
int n;
cin>>n;
for(int i=1;i<=n;i++)cin>>a[i];
for(int i=1;i<=n;i++)b[i]=a[i]-a[i-1];
ll ans=0;
for(int i=2;i<=n;i++){
if(b[i]>0)ans+=b[i];
else if(b[i]<0){
ans-=b[i];
b[1]+=b[i];
}
}
cout<<ans+abs(b[1])<<endl;
}
int main(){
cin>>T;while(T--)
slove();
return 0;
}
边栏推荐
- EasyCVR平台通过接口编辑通道出现报错“ID不能为空”,是什么原因?
- Video fusion cloud platform easycvr adds multi-level grouping, which can flexibly manage access devices
- Pytest learning ----- pytest confitest of interface automation test Py file details
- 李书福为何要亲自挂帅造手机?
- How to use scroll bars to dynamically adjust parameters in opencv
- EasyCVR电子地图中设备播放器loading样式的居中对齐优化
- 【Elastic】Elastic缺少xpack无法创建模板 unknown setting index.lifecycle.name index.lifecycle.rollover_alias
- Hongmeng introduction and development environment construction
- Pyspark operator processing spatial data full parsing (4): let's talk about spatial operations first
- RB157-ASEMI整流桥RB157
猜你喜欢
2022年大厂Android面试题汇总(二)(含答案)
Wordcloud colormap color set and custom colors
EasyCVR接入设备开启音频后,视频无法正常播放是什么原因?
Scratch epidemic isolation and nucleic acid detection Analog Electronics Society graphical programming scratch grade examination level 3 true questions and answers analysis June 2022
Virtual machine startup prompt probing EDD (edd=off to disable) error
Pytest learning ----- detailed explanation of the request for interface automation test
【MySQL入门】第一话 · 初入“数据库”大陆
10 advanced concepts that must be understood in learning SQL
BearPi-HM_ Nano development board "flower protector" case
Yarn: unable to load file d:\programfiles\nodejs\yarn PS1, because running scripts is prohibited on this system
随机推荐
Pytorch extract middle layer features?
Run xv6 system
How to solve the error "press any to exit" when deploying multiple easycvr on one server?
TCP connection is more than communicating with TCP protocol
学 SQL 必须了解的 10 个高级概念
Kali2021 installation and basic configuration
Concept and basic knowledge of network layering
Manifest of SAP ui5 framework json
李书福为何要亲自挂帅造手机?
Awk command exercise
Grafana 9 is officially released, which is easier to use and more cool!
The NTFS format converter (convert.exe) is missing from the current system
C# NanoFramework 点灯和按键 之 ESP32
开源与安全的“冰与火之歌”
Unity粒子特效系列-闪星星的宝箱
Selected technical experts from China Mobile, ant, SF, and Xingsheng will show you the guarantee of architecture stability
Openharmony developer documentation open source project
Chrome prompts the solution of "your company management" (the startup page is bound to the company's official website and cannot be modified)
Grafana 9 正式发布,更易用,更酷炫了!
There is a gap in traditional home decoration. VR panoramic home decoration allows you to experience the completion effect of your new house