蓝桥杯算法题目练习
2022练习题
1161: 三值排序
题目描述
给一个长度为n的数组,其中数组各元素的值仅为1、2、3。
求排成升序的最少交换次数。输入格式
第一行为正整数n,不超过1000。
接下来n行,每行一个整数表示数组元素。输出格式
输出一个数字表示答案。
**思路:**记录排序后是1/2/3的区域,遍历原列表,如果不在自己对应的区域,则先去自己应该在的区域里面找,找到了则交换,找不到再从全局查找。
代码:
if __name__ == "__main__":
n = int(input())
l = []
dic = {}
result = 0
for i in range(n):
j = int(input())
l.append(j)
if dic.get(j):
dic[j] = 1
else:
dic[j] = 1
count = 1
offset = 0
for i in range(n):
while not dic.get(count) and count <= 3:
count = 1
if i == dic[count] offset:
offset = dic[count]
count = 1
if l[i] != count:
begin = offset
c = count
while c < l[i]:
begin = dic[c]
c = 1
if c == 3:
end = n
else:
c = 1
end = begin dic[c]
for j in range(begin, end):
if l[j] == count:
l[i], l[j] = l[j], l[i]
result = 1
break
if l[i] != count:
for j in range(dic[count] offset, n):
if l[j] == count:
l[i], l[j] = l[j], l[i]
result = 1
break
print(result)
2026: [蓝桥杯2022初赛] 青蛙过河
题目描述
小青蛙住在一条河边,它想到河对岸的学校去学习。小青蛙打算经过河里的石头跳到对岸。
河里的石头排成了一条直线,小青蛙每次跳跃必须落在一块石头或者岸上。
不过,每块石头有一个高度,每次小青蛙从一块石头起跳,这块石头的高度就会下降1。
当石头的高度下降到0 时小青蛙不能再跳到这块石头上(某次跳跃后使石头高度下降到0 是允许的)。
小青蛙一共需要去学校上x 天课,所以它需要往返2x 次。
当小青蛙具有一个跳跃能力y 时,它能跳不超过y 的距离。
请问小青蛙的跳跃能力至少是多少才能用这些石头上完x 次课。输入格式
输入的第一行包含两个整数n, x,分别表示河的宽度和小青蛙需要去学校的天数。
请注意2x 才是实际过河的次数。
第二行包含n - 1 个非负整数H1, H2, … , Hn-1。
其中Hi > 0 表示在河中与小青蛙的家相距i 的地方有一块高度为Hi 的石头,Hi = 0 表示这个位置没有石头。
30%的测试数据:n≤100
60%的测试数据:n≤1000
100%的测试数据:1≤n≤100000,1≤x≤109,0≤Hi≤104输出格式
输出一行,包含一个整数,表示小青蛙需要的最低跳跃能力。
**思路:**二分查找,保证每个区间的石头数值总和大于2*x即可。
代码:
def m(y):
for i in range(y, n):
if sumlist[i] - sumlist[i-y] < 2 * x:
return False
return True
if __name__ == "__main__":
n, x = map(int, input().split())
stones = list(map(int, input().split()))
sumlist = [0, stones[0]]
for i in range(1, len(stones)):
sumlist.append(stones[i] sumlist[i])
l = 0
r = 100000
while l <= r:
mid = (l r) // 2
if m(mid):
r = mid - 1
else:
l = mid 1
print(l)
1819: [NewOJ Week 6] 推箱子
题目描述
在一个高度为H的箱子前方,有一个长和高为N的障碍物。
障碍物的每一列存在一个连续的缺口,第i列的缺口从第l各单位到第h个单位(从底部由0开始数)。
现在请你清理出一条高度为H的通道,使得箱子可以直接推出去。
请输出最少需要清理的障碍物面积。
如下图为样例中的障碍物,长和高度均为5,箱子高度为2。(不需要考虑箱子会掉入某些坑中)
最少需要移除两个单位的障碍物可以造出一条高度为2的通道。
输入格式
输入第一行为两个正整数N和H,表示障碍物的尺寸和箱子的高度,1≤H≤N≤1000000。
接下来N行,每行包含两个整数li和hi,表示第i列缺口的范围,0≤li≤hi<N。输出格式
输出一个数字表示答案。
**思路:**使用差分数组,最后转换成前缀和数组,然后求出区间和的最大值即可。
代码:
if __name__ == "__main__":
N, H = map(int, input().split())
li = [0 for i in range(N)]
for i in range(N):
l, h = map(int, input().split())
li[l] = 1
li[h 1] -= 1
li[1] = li[0]
for i in range(2, N):
li[i] = li[i-1]
li[i-1] = li[i-2]
li[-1] = li[-2]
mx = li[H-1]
for i in range(H, N):
mx = max(mx, li[i] - li[i-H])
print(H*N-mx)
这篇好文章是转载于:学新通技术网
- 版权申明: 本站部分内容来自互联网,仅供学习及演示用,请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系,请提供相关证据及您的身份证明,我们将在收到邮件后48小时内删除。
- 本站站名: 学新通技术网
- 本文地址: /boutique/detail/tanhgehhha
-
photoshop保存的图片太大微信发不了怎么办
PHP中文网 06-15 -
Android 11 保存文件到外部存储,并分享文件
Luke 10-12 -
word里面弄一个表格后上面的标题会跑到下面怎么办
PHP中文网 06-20 -
《学习通》视频自动暂停处理方法
HelloWorld317 07-05 -
photoshop扩展功能面板显示灰色怎么办
PHP中文网 06-14 -
微信公众号没有声音提示怎么办
PHP中文网 03-31 -
excel下划线不显示怎么办
PHP中文网 06-23 -
excel打印预览压线压字怎么办
PHP中文网 06-22 -
怎样阻止微信小程序自动打开
PHP中文网 06-13 -
TikTok加速器哪个好免费的TK加速器推荐
TK小达人 10-01