题目描述
时间：1s 空间：256M
题目描述：
小信有一个长度为
𝑛
n 的数组
𝑎
a，他想把这个数组变成回文数组。
他可以操作若干次，每次操作，选择一个区间
[
𝐿
,
𝑅
]
[L,R]，把
𝑎
𝑙
,
𝑎
𝑙
+
1
,
…
,
𝑎
𝑟
a
l
,a
l+1
,…,a
r
都加
1
1。
小信想知道最少需要操作多少次，才能把这个数组变成回文数组。
输入格式：
第一行包含一个整数
𝑛
n。
第二行包含长度为
𝑛
n 的数组
𝑎
1
,
𝑎
2
,
…
,
𝑎
𝑛
a
1
,a
2
,…,a
n
。
输出格式：
输出一个整数表示答案。
样例1输入：
6
2 6 4 3 4 1
样例1输出：
2
样例2输入：
3
1 10 1
样例2输出：
0
约定：
对于100%的数据，
1
≤
𝑛
≤
3
⋅
1
0
5
1≤n≤3⋅10
5
,
1
≤
𝑎
𝑖
≤
1
0
9
1≤a
i
≤10
9
对于样例1：选择
[
3
,
6
]
[3,6] 和
[
4
,
5
]
[4,5]，数组变成
[
2
,
6
,
5
,
5
,
6
,
2
]
[2,6,5,5,6,2]
#include<bits/stdc++.h>
using namespace std;
int a[300005],n,mx=-0x7f7f7f7f,tmp;
bool f;
int main(){
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i];
}
for(int i=1;i<=n;i++){
a[i]-=min(a[i],a[n-i+1]);
}
for(int i=1;i<=n;i++){
if(a[i]){
mx=max(mx,a[i]);
f=1;
}else if(f){
tmp+=mx;
mx=-0x7f7f7f7f;
f=0;
}
}
cout<<tmp;
return 0;
}
