蓝桥杯算法题目练习_蓝桥杯题目

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)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43

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)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

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)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16