微博网站可以做兼职吗,wordpress获取新密码错误,江苏华能建设集团有限公司网站,成武网站建设题目
设计一个算法#xff0c;用最少数量的矩形覆盖一系列宽度为d、高度为w的矩形建筑物侧墙#xff0c;且矩形不能超出边界。
核心思路
考虑这种结构 前面递增后面一个与前面的某个高度一致#xff0c;这时候考虑最下面的覆盖#xff08;即都是从最下面向上覆盖#…题目
设计一个算法用最少数量的矩形覆盖一系列宽度为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
