当前位置:网站首页>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;
}
边栏推荐
- Compile and build, from the bottom to the top
- Cool Lehman has a variety of AI digital human images to create a vr virtual exhibition hall with a sense of technology
- Kali2021 installation and basic configuration
- 面试突击63:MySQL 中如何去重?
- Interview assault 63: how to remove duplication in MySQL?
- Video fusion cloud platform easycvr adds multi-level grouping, which can flexibly manage access devices
- MySQL error reporting solution
- Solution qui ne peut pas être retournée après la mise à jour du navigateur Web flutter
- How to submit data through post
- 基于STM32+华为云IOT设计的智能路灯
猜你喜欢
[ASM] introduction and use of bytecode operation classwriter class
[rapid environment construction] openharmony 10 minute tutorial (cub pie)
Pytorch extract middle layer features?
JMeter interface test response data garbled
kivy教程之在 Kivy 中支持中文以构建跨平台应用程序(教程含源码)
Unity tips - draw aiming Center
Zen integration nails, bugs, needs, etc. are reminded by nails
Reppoints: advanced order of deformable convolution
The easycvr platform reports an error "ID cannot be empty" through the interface editing channel. What is the reason?
Wordcloud colormap color set and custom colors
随机推荐
There is a gap in traditional home decoration. VR panoramic home decoration allows you to experience the completion effect of your new house
C # nanoframework lighting and key esp32
OpenEuler 会长久吗
Kernel link script parsing
Virtual machine startup prompt probing EDD (edd=off to disable) error
FlutterWeb瀏覽器刷新後無法回退的解决方案
Grafana 9 is officially released, which is easier to use and more cool!
Summary of Android interview questions of Dachang in 2022 (II) (including answers)
scratch疫情隔离和核酸检测模拟 电子学会图形化编程scratch等级考试三级真题和答案解析2022年6月
The easycvr authorization expiration page cannot be logged in. How to solve it?
Appium automated test scroll and drag_ and_ Drop slides according to element position
Debug xv6
基于STM32+华为云IOT设计的智能路灯
酷雷曼多种AI数字人形象,打造科技感VR虚拟展厅
Mysqlimport imports data files into the database
遠程代碼執行滲透測試——B模塊測試
Getting started with pytest ----- test case pre post, firmware
Awk command exercise
VR panoramic wedding helps couples record romantic and beautiful scenes
In terms of byte measurement with an annual salary of 30W, automated testing can be learned in this way