蓝桥杯备考冲刺必刷题(Python) | 3236 小蓝的零花钱

学习Python从娃娃抓起！记录下蓝桥杯备考比赛学习过程中的题目，记录每一个瞬间。

附上汇总贴：蓝桥杯备考冲刺必刷题（Python） | 汇总-CSDN博客

【题目描述】

小蓝和小桥正在玩一个游戏，他们有一个长度为$n$的序列，其中既有偶数也有奇数，且偶数和奇数的数量相等。

小蓝有一些零花钱，他可以用这些钱来做一个特殊的操作：他在序列中选取一个位置，然后在这个位置上将序列分成两段，要求每一段中偶数和奇数的数量都相等。小蓝想要用他的零花钱尽可能多地进行这个操作，但每次操作都需要花费代价。具体而言，每次选取的位置可以看成是对序列进行切割，切割需要花费的代价为切割两端的元素的差的绝对值。小蓝想知道，在他的预算范围内，最多能进行多少次操作。

请你帮助小蓝计算最多可以进行的操作次数。

【输入】

第一行包含两个整数$n$和$B(2\le n\le 100,1\le B\le 100)$，表示序列的长度和小蓝拥有的零花钱数。

第二行包含$n$个整数$a_1,a_2,\dots,a_n(1\le a_i\le 100)$，表示给定的序列(保证在这$n$个元素中奇数的个数等于偶数的个数)。

【输出】

输出一个整数，表示在小蓝的预算范围内，能够进行的最多操作次数。

【输入样例】

6 3
1 2 3 4 5 6

【输出样例】

2

【代码详解】

n, b = [int(i) for i in input().split()]  # 输入n和b
a = [0 for i in range(105)]  # 初始化a数组
ls = [int(i) for i in input().split()]  
for i in range(1, n+1):  # 给a数组赋值
    a[i] = ls[i-1]
odd = [0 for i in range(105)]  # 初始化奇数个数数组
even = [0 for i in range(105)]  # 初始化偶数个数数组
c = [0 for i in range(105)]  # 初始化切割代价数组
for i in range(1, n+1):  # 遍历n个零花钱
    if a[i]%2==1:  # 进行奇偶判断
        odd[i]=odd[i-1]+1
        even[i]=even[i-1]
    else:
        odd[i]=odd[i-1]
        even[i]=even[i-1]+1
mark = 0
for i in range(1, n):  # 遍历奇偶数组
    if odd[i]==even[i]:  # 对于奇偶数相等的位置，则可以切割
        c[mark]=abs(a[i]-a[i+1])  # 计算a[i]与a[i+1]的绝对值，并记录到c数组中
        mark+=1
c = sorted(c[:mark])  # 对c数组按照从小到大方式排序
tot = 0 
cnt=0
for i in range(mark):  # 遍历c数组
    if tot+c[i]<=b:  # 如果tot加上c[i]可以满足小于等于b
        tot+=c[i]  # 则进行累加
        cnt+=1  # 切割数自增1
    else:  # 否则退出循环
        break
print(cnt)  # 输出切割数

【运行结果】

6 3
1 2 3 4 5 6
2