小A的楼房外有一大片施工工地，工地上有N栋待建的楼房。每天，这片工地上的房子拆了又建、建了又拆。他经常无聊地看着窗外发呆，数自己能够看到多少栋房子。   为了简化问题，我们考虑这些事件发生在一个二维平面上。小A在平面上(0,0)点的位置，第i栋楼房可以用一条连接(i,0)和(i,Hi)的线段表示，其中Hi为第i栋楼房的高度。 如果这栋楼房上任何一个高度大于0的点与(0,0)的连线没有与之前的线段相交，那么这栋楼房就被认为是可见的。   施工队的建造总共进行了M天。初始时，所有楼房都还没有开始建造，它们的高度均为0。 在第i天，建筑队将会将横坐标为Xi的房屋的高度变为Yi(高度可以比原来大---修建，也可以比原来小---拆除，甚至可以保持不变---建筑队这天什么事也没做)。 请你帮小A数数每天在建筑队完工之后，他能看到多少栋楼房？ 输入 第一行两个正整数N,M 接下来M行，每行两个正整数Xi,Yi 输出 M行，第i行一个整数表示第i天过后小A能看到的楼房有多少栋 样例输入 复制 3 4 2 4 3 6 1 1000000000 1 1

以下是解决该问题的Python代码： ```python # 读取输入的N和M N, M = map(int, input().split()) # 初始化每栋楼的高度为0 heights = [0] * (N + 1) # 循环处理M天的建造操作 for _ in range(M): # 读取当天处理的楼的横坐标Xi和目标高度Yi Xi, Yi = map(int, input().split()) # 更新对应楼的高度 heights[Xi] = Yi # 用于记录当前最大斜率 max_slope = 0 # 用于记录可见楼的数量 visible_count = 0 # 遍历每栋楼 for i in range(1, N + 1): if heights[i] > 0: # 计算当前楼的斜率 slope = heights[i] / i # 如果当前斜率大于最大斜率，则该楼可见 if slope > max_slope: visible_count += 1 # 更新最大斜率 max_slope = slope # 输出当天可见楼的数量 print(visible_count) ``` 代码解释： 1. 输入读取：首先读取两个整数`N`和`M`，分别表示待建楼房的数量和建造的天数。 2. 高度初始化：创建一个长度为`N + 1`的列表`heights`，用于存储每栋楼的高度，初始值都为0。 3. 循环处理建造操作：对于每一天，读取要处理的楼的横坐标`Xi`和目标高度`Yi`，并更新`heights`列表中对应楼的高度。 4. 计算可见楼的数量：遍历每栋楼，对于高度大于0的楼，计算其与原点`(0, 0)`连线的斜率。如果该斜率大于之前记录的最大斜率，则该楼可见，更新最大斜率并增加可见楼的数量。 5. 输出结果：输出当天可见楼的数量。 复杂度分析： - 时间复杂度：$O(M * N)$，其中`M`是建造的天数，`N`是待建楼房的数量。因为对于每一天，都需要遍历所有的楼来计算可见楼的数量。 - 空间复杂度：$O(N)$，主要用于存储每栋楼的高度。 [2025-12-12 18:42:17 | AI问答 | 539点数解答]