题目1 回文数组
小蓝在无聊时随机生成了一个长度为 n 的整数数组,数组中的第 i 个数为 ai,他觉得随机生成的数组不太美观,想把它变成回文数组,也是就对于任意 i∈[1,n] 满足 a i = a n − i + 1 a_i=a_{n−i}+1 ai=an−i+1。
小蓝一次操作可以指定相邻的两个数,将它们一起加 1 或减 1;也可以只指定一个数加 1 或减 1,请问他最少需要操作多少次能把这个数组变成回文数组?
输入格式
输入的第一行包含一个正整数 n。
第二行包含 n 个整数 a1,a2,…,an,相邻整数之间使用一个空格分隔。
输出格式
输出一行包含一个整数表示答案。
数据范围
对于 20% 的评测用例,1≤n≤10。
对于所有评测用例, 1 ≤ n ≤ 1 0 5 , − 1 0 6 ≤ a i ≤ 1 0 6 1≤n≤10^5,−10^6≤a_i≤10^6 1≤n≤105,−106≤ai≤106。
输入样例:
4
1 2 3 4
输出样例:
3
样例解释
第一次操作将 a1,a2 加 1,变为 2,3,3,4;
后面两次操作将 a1 加 1,变为 4,3,3,4。
思路
+1
的操作等价于-1
,例如:1 2 3 4 ➡️1 2 2 1 or 1 2 3 4 ➡️4 3 3 4- 那么我们只选择一种操作,
-1
- 从两边分别统计
差值
,比如对于样例,0 0 1 2 - 遍历,进行
-1
操作,对于连续的两个位置-1
,当做一次操作,最终结果为0 0 0 1 - 遍历最终位置为倒数第二个元素,此时如果倒数第一个元素不为0,单独进行
-1
操作
python代码
import os
import sys
n=int(input())
data=list(map(int,input().split()))
a=[0]*(n)
ans=0
l,r=0,n-1
while l<=n//2 and r>=n//2:t=min(data[l],data[r])data[l]-=tif l!=r:data[r]-=tl+=1r-=1
for i in range(n-1):t=data[i]if t>0:ans+=tdata[i+1]-=min(t,data[i+1])
if data[n-1]>0:ans+=data[n-1]
print(ans)
知识点
蓝桥杯笔记:蓝桥杯备赛笔记
- 思维?贪心?回文数?