欢迎来到尧图网

客户服务 关于我们

您的位置:首页 > 健康 > 养生 > 第十五届蓝桥杯大赛软件赛省赛Python 大学 C 组:5.回文数组

第十五届蓝桥杯大赛软件赛省赛Python 大学 C 组:5.回文数组

2025/4/5 11:33:36 来源:https://blog.csdn.net/qq_47461600/article/details/147003271  浏览:    关键词:第十五届蓝桥杯大赛软件赛省赛Python 大学 C 组:5.回文数组

题目1 回文数组

小蓝在无聊时随机生成了一个长度为 n 的整数数组,数组中的第 i 个数为 ai,他觉得随机生成的数组不太美观,想把它变成回文数组,也是就对于任意 i∈[1,n] 满足 a i = a n − i + 1 a_i=a_{n−i}+1 ai=ani+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 1n105106ai106

输入样例:
4
1 2 3 4
输出样例:
3
样例解释

第一次操作将 a1,a2 加 1,变为 2,3,3,4;

后面两次操作将 a1 加 1,变为 4,3,3,4。


思路

  1. +1的操作等价于-1,例如:1 2 3 4 ➡️1 2 2 1 or 1 2 3 4 ➡️4 3 3 4
  2. 那么我们只选择一种操作,-1
  3. 从两边分别统计差值,比如对于样例,0 0 1 2
  4. 遍历,进行-1操作,对于连续的两个位置-1,当做一次操作,最终结果为0 0 0 1
  5. 遍历最终位置为倒数第二个元素,此时如果倒数第一个元素不为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)

知识点

蓝桥杯笔记:蓝桥杯备赛笔记

  1. 思维?贪心?回文数?

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com

热搜词