题解 | #铺地毯#

这是一道“覆盖层查询”问题，核心是找到最后铺设（最上层）的覆盖目标点的地毯，解题思路与代码实现如下：

解题思路一：正向推演

这个思路的核心是：

1. 先收集所有信息：读取所有地毯的数据并存储起来。
2. 明确目标：最后读取要查询的目标点坐标。
3. 正向模拟检查：从第一块地毯开始，依次检查每一块地毯是否能覆盖目标点。如果能覆盖，就用当前地毯的编号更新结果。因为我们是正向遍历，所以后覆盖的地毯编号会自动覆盖掉前面的结果，最终保留的就是最后（最上层）覆盖该点的地毯编号。

代码实现（Python）

# 1. 读取地毯数量
n = int(input())

# 2. 读取所有地毯的信息并存储起来
# 我们用一个列表来存储，每个元素是一个包含(a, b, g, k, 编号)的元组
carpets = []
for i in range(n):
    a, b, g, k = map(int, input().split())
    carpets.append( (a, b, g, k, i + 1) ) # i+1 是地毯的编号

# 3. 最后读取目标点的坐标
x, y = map(int, input().split())

result = -1 # 初始化结果为-1，表示未被任何地毯覆盖

# 4. 正向遍历所有地毯，模拟铺设和覆盖检查过程
for carpet in carpets:
    a, b, g, k, id = carpet
    # 检查当前地毯是否覆盖目标点 (x, y)
    if a <= x <= a + g and b <= y <= b + k:
        # 如果覆盖，则更新结果为当前地毯的编号
        # 因为是正向遍历，后面的地毯会覆盖前面的，所以直接赋值即可
        result = id

# 5. 输出最终结果
print(result)

解题思路二：逆向推导

1. 理解地毯覆盖范围：每个地毯的左下角为 (a, b)，x方向长度为 g、y方向长度为 k，因此它覆盖的区域是：
   • x范围：[a, a+g]（包含端点）
   • y范围：[b, b+k]（包含端点）
2. 查询策略：由于地毯按编号从小到大铺设（后铺的覆盖先铺的），因此从最后一个地毯（编号最大）往前遍历，第一个覆盖目标点的地毯就是最上层的，直接返回其编号。
3. 判断条件：若目标点 (x, y) 满足 a ≤ x ≤ a+g 且 b ≤ y ≤ b+k，则该地毯覆盖此点。

代码实现（Python）

# 读取地毯数量n
n = int(input())
# 存储所有地毯的信息（a, b, g, k）
carpets = []
for _ in range(n):
    a, b, g, k = map(int, input().split())
    carpets.append((a, b, g, k))
# 读取查询的点(x, y)
x, y = map(int, input().split())

# 从最后一个地毯（最上层）往前遍历
for i in range(n-1, -1, -1):
    a, b, g, k = carpets[i]
    # 判断当前地毯是否覆盖目标点
    if a <= x <= a + g and b <= y <= b + k:
        print(i + 1)  # 地毯编号是索引+1
        exit()

# 遍历完所有地毯都未覆盖
print(-1)

该方法的时间复杂度为 O(n)（最坏情况遍历所有地毯），但实际中通常会提前找到结果，效率较高。

解题思路二：优化

我们可以换一个更偏向“数据结构优化”的思路。这个思路的核心是提前对地毯的位置信息进行预处理，以便在查询时能够更快速地定位，而不是线性扫描所有地毯。

这个方法特别适用于查询次数非常多的场景（例如，有上万个查询点），可以将单次查询的时间复杂度从 O(N) 降低到 O(log N + K)，其中 K 是最终需要检查的候选地毯数量，通常 K 很小。

优化思路：空间换时间 + 二分查找

核心想法

1. 问题分解：一个点 (x, y) 被地毯覆盖，需要满足两个条件： a. x 坐标在地毯的 x 轴覆盖范围 [a, a+g] 内。 b. y 坐标在地毯的 y 轴覆盖范围 [b, b+k] 内。

2. 预处理：

   • 我们可以将所有地毯按照其 x 轴的右边界 a+g 进行排序。
   • 同时，我们单独存储每个地毯的 x 轴左边界 a 和 y 轴覆盖范围 [b, b+k] 以及它的编号。

3. 查询时：

   • 对于查询点 (x, y)，我们首先利用 二分查找 在排序好的地毯列表中，快速找到所有 x 轴右边界 a+g 大于等于 x 的地毯。因为如果一个地毯的右边界都小于 x，它绝不可能覆盖 x。
   • 经过这一步筛选，我们得到了一个候选地毯列表。这个列表中的地毯都满足 a+g >= x。
   • 接下来，我们只需要遍历这个小得多的候选列表，检查两个条件：
     1. 地毯的 x 轴左边界 a 是否 <= x。
     2. 点的 y 坐标是否在地毯的 y 轴范围 [b, b+k] 内。
   • 在遍历候选列表时，我们从后往前遍历（因为我们关心的是最后铺设的地毯），一旦找到一个完全满足条件的地毯，就可以立即返回它的编号。

代码实现（Python）

import bisect

# 1. 读取输入并进行预处理
n = int(input())
carpets = []
for idx in range(n):
    a, b, g, k = map(int, input().split())
    # 存储：(x轴右边界, x轴左边界, y轴左边界, y轴右边界, 原始编号)
    carpets.append((a + g, a, b, b + k, idx + 1))

# 2. 关键：按照 x 轴右边界进行排序
carpets.sort()

# 读取查询点
x, y = map(int, input().split())

# 3. 使用二分查找快速定位候选地毯
# bisect.bisect_left 返回第一个 >= x 的元素的索引
# 我们的列表是按 a+g 排序的，所以从这个索引开始的地毯都满足 a+g >= x
candidate_index = bisect.bisect_left(carpets, (x,))

# 4. 遍历候选列表（从后往前，以找到最后铺设的地毯）
# 注意：这里的切片操作会创建一个新列表，如果n非常大，这里可以优化为直接用索引遍历
for carpet in reversed(carpets[candidate_index:]):
    a_plus_g, a, b, b_plus_k, original_id = carpet
    # 检查 x 是否在 [a, a+g] 内，以及 y 是否在 [b, b+k] 内
    if a <= x and b <= y <= b_plus_k:
        print(original_id)
        exit()

# 如果没有找到任何覆盖的地毯
print(-1)

方法对比与分析