网站开发面试自助建站系统注册

题目

设计一个算法，用最少数量的矩形覆盖一系列宽度为d、高度为w的矩形建筑物侧墙，且矩形不能超出边界。

核心思路

考虑这种结构

前面递增后面一个与前面的某个高度一致，这时候考虑最下面的覆盖（即都是从最下面向上覆盖）

考虑到使用栈，这里我们用列表代替

当栈不为空并且新元素比栈顶小，这时候存在这种可能结构成立，
对每个墙循环，如果新元素比栈顶元素大，就进栈；
反之，如果新元素比栈顶元素小，就使得栈顶元素出栈，继续比较新栈顶元素与当前使用新元素的大小，一直到比较到当前使用新元素和之前的某个元素的大小相同，此时计数器+1，表示找到这种结构+1

另外向上因为与数量一致，所以这里不考虑

伪代码

定义一个函数 main：定义一个变量 n，用于存储输入的整数。定义一个变量 ans，初始化为 0，用于存储最终答案。定义一个空列表 st，用于模拟栈结构。对于从 1 到 n 的每个整数 i：读取两个整数 d 和 w，并将它们分别存储到变量 d 和 w 中。当列表 st 不为空且 w 小于等于 st 中最后一个元素时：如果 st 中最后一个元素等于 w：将 ans 的值增加 1。从 st 中移除最后一个元素，因为当前 w 值破坏了递增结构。将 w 添加到 st 的末尾。打印 n 减去 ans 的结果。如果这个脚本是主程序：调用 main 函数。

CODE

def main():n = int(input())# 这种结构有多少种ans = 0st = []for i in range(1, n + 1):d, w = map(int, input().split())# 列表类似栈的结构while st and w <= st[-1]:# 找到该种结构种类数+1if st[-1] == w:ans += 1# pop掉，因为该种结构要求前面都是递增，而这里当前使用新元素已经是破坏了# 递增结构，所以直接丢掉，准备下一次的# 最后栈是空的，上面循环直接刷到最前面了st.pop()st.append(w)print(n - ans)if __name__ == "__main__":main()

END