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≤10
9，0≤Hi≤10
4
输出格式
输出一行，包含一个整数，表示小青蛙需要的最低跳跃能力。
**思路:**二分查找，保证每个区间的石头数值总和大于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)