LCCUP 2021 春季编程大赛——个人赛

发表于 | 分类于

最近一个多月刷了三百多道题，正好赶上LeetCode举办的春季赛，也算是对自己刷题成果的小小检验。一共2.5小时，5道题，参赛选手9932人，排名180+。

LCP 28 采购方案

排序 -> 有序数组中，两数之和小于等于target的方案数 -> 双指针
时间复杂度：O(n)，空间复杂度：O(1)

LCP 29 乐团站位

数学题。先统计外层人数，然后统计当前层人数

外层：
层数：outside = min(xPos, yPos, num - xPos - 1, num - yPos - 1)
最外层人数：(num - 1) * 4
最里面的外层的人数：(num - 2 * (outside - 1) - 1) * 4
所以总人数：(num - 1 + num - 2 * (outside - 1) - 1) * outside * 2

当前层：
当前层总人数：cur_circle_count = (num - 2 * outside - 1) * 4
(xPos, yPos)和(outside, outside)之间人数（上半圈）：dist = (xPos - outside) + (yPos - outside)
(xPos, yPos)和(outside, outside)之间人数（下半圈）：cur_circle_count - dist

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution:
    def orchestraLayout(self, num: int, xPos: int, yPos: int) -> int:
        total_count = 0

        # 外层人数
        outside = min(xPos, yPos, num - xPos - 1, num - yPos - 1)
        total_count += ((num - 1 + num - 2 * (outside - 1) - 1) * outside * 2) % 9

        # 当前层人数
        cur_circle_count = (num - 2 * outside - 1) * 4
        dist = (xPos - outside) + (yPos - outside)
        if xPos > yPos:
            dist = cur_circle_count - dist

        total_count += (dist + 1) % 9
        total_count = total_count % 9

        return total_count if total_count != 0 else 9

LCP 30 魔塔游戏

贪心。
首先判断所有血量之和是否大于等于0，如果不是，则一定无法访问所有房间。
用一个int变量存储当前血量，一个最小堆存储所有走过的、未调整到最后的房间的血量。如果能走到下一个房间，则直接走；否则从最小堆中取出最小元素，将其调整到最后。

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
import heapq

class Solution:
    def magicTower(self, nums: List[int]) -> int:
        if not nums:
            return 0

        if sum(nums) + 1 < 0: # 所有血量之和小于0，无法访问所有房间
            return -1

        nums_len = len(nums)

        cur_blood = 1
        remove = 0
        min_heap = []

        for x in nums:
            cur_blood += x
            heapq.heappush(min_heap, x)

            if cur_blood < 0:
                cur_blood -= heapq.heappop(min_heap)
                remove += 1

        return remove