铺地毯(luogu-P1003)

NOIP 2011 提高组真题，枚举与模拟考点应用，重点理解逆向思维（倒序遍历）的优化策略。GESP 三、四级及以上考生可以练习。题目难度⭐⭐★☆☆，洛谷难度等级普及−。

luogu-P1003 [NOIP 2011 提高组] 铺地毯

题目要求

题目描述

为了准备一个独特的颁奖典礼，组织者在会场的一片矩形区域（可看做是平面直角坐标系的第一象限）铺上一些矩形地毯。一共有 $n$ 张地毯，编号从 $1$ 到 $n$ 。现在将这些地毯按照编号从小到大的顺序平行于坐标轴先后铺设，后铺的地毯覆盖在前面已经铺好的地毯之上。
地毯铺设完成后，组织者想知道覆盖地面某个点的最上面的那张地毯的编号。注意：在矩形地毯边界和四个顶点上的点也算被地毯覆盖。

输入格式

输入共 $n + 2$ 行。
第一行，一个整数 $n$ ，表示总共有 $n$ 张地毯。
接下来的 $n$ 行中，第 $i+1$ 行表示编号 $i$ 的地毯的信息，包含四个整数 $a ,b ,g ,k$ ，每两个整数之间用一个空格隔开，分别表示铺设地毯的左下角的坐标 $(a, b)$ 以及地毯在 $x$ 轴和 $y$ 轴方向的长度。
第 $n + 2$ 行包含两个整数 $x$ 和 $y$ ，表示所求的地面的点的坐标 $(x, y)$ 。

输出格式

输出共 $1$ 行，一个整数，表示所求的地毯的编号；若此处没有被地毯覆盖则输出 -1。

输入输出样例 #1

输入 #1

输出 #1

输入输出样例 #2

输入 #2

输出 #2

-1

说明/提示

【样例解释 1】

如下图， $1$ 号地毯用实线表示， $2$ 号地毯用虚线表示， $3$ 号用双实线表示，覆盖点 $(2,2)$ 的最上面一张地毯是 $3$ 号地毯。

【数据范围】

对于 $30\%$ 的数据，有 $n \le 2$ 。
对于 $50\%$ 的数据， $0 \le a, b, g, k \le 100$ 。
对于 $100\%$ 的数据，有 $0 \le n \le 10^4$ , $0 \le a, b, g, k \le {10}^5$ 。

noip2011 提高组 day1 第 $1$ 题。

题目分析

这道题的核心考点是模拟和枚举。题目要求找出覆盖目标点 $(x, y)$ 的“最上面”那张地毯。因为地毯是按编号从小到大顺序依次铺设的，后铺的地毯会覆盖在先铺的地毯之上，所以最上面的地毯也就是最后铺设且覆盖了该点的地毯。

1. 数学模型（点在矩形内的判断）

地毯 $i$ 的左下角坐标为 $(a_i, b_i)$ ，在 $x$ 轴和 $y$ 轴方向的长度分别为 $g_i$ 和 $k_i$ 。因此，它覆盖的矩形区域是一个横坐标从 $a_i$ 到 $a_i + g_i$ ，纵坐标从 $b_i$ 到 $b_i + k_i$ 的范围。判断给定点 $(x, y)$ 是否在这张地毯上的条件为（包含边界）：

a_i \le x \le a_i + g_i \quad \text{且} \quad b_i \le y \le b_i + k_i

只要满足这个条件，点 $(x, y)$ 就被编号为 $i$ 的地毯覆盖。

2. 解题策略（逆向思维优化）

最直观的想法是“正向模拟”：开一个巨大的二维数组代表地板，每拿到一张地毯，就把地毯覆盖区域的格子都填上该地毯的编号（即所谓的“刷表法”）。最后查询 $(x, y)$ 格子里的编号。但题目数据范围中坐标高达 $10^5$ ，如果定义二维数组会需要 $10^{10}$ 个元素，这会导致严重超内存（MLE）和严重超时（TLE）！

正确的解题思路无需真的去“铺”地毯，只需要记录下每张地毯的信息，然后针对所求的单个点 $(x,y)$ 进行查询即可。特别地，这道题使用 逆向思维（倒序枚举） 会非常巧妙且高效：

接收并保存所有地毯的信息。
从最后一张铺设的地毯（即编号 $n$ 的地毯）开始，倒序向前遍历（一直到编号 $1$ ）。
对遇到的每一张地毯，检查点 $(x, y)$ $(x, y)$ 是否在它的覆盖范围内：
- 第一张满足条件的地毯，必定是所有覆盖该点的地毯中编号最大的，也就是处于最上面的地毯。
- 此时直接记录答案为该地毯编号，并使用 break 提前终止循环即可（因为我们只需要找最上面的那一张）。
如果遍历完所有地毯都没有满足条件的，说明该点未被任何地毯覆盖，输出初始值 -1 即可。

3. 复杂度分析

时间复杂度： $O(n)$ 。读取 $n$ 张地毯信息需要 $O(n)$ 的时间；查找答案时，最坏情况下（点被第一张地毯覆盖或未被覆盖）需要完整倒序遍历 $n$ 次，操作次数也是 $O(n)$ 级别。在 $n \le 10^4$ 的数据规模下，最大计算量仅在两万次左右，远远小于 C++ 1 秒内 $10^8$ 次的运行限制，效率极高。
空间复杂度： $O(n)$ 。不需要创建巨大的二维地图数组，只需要保存每张地毯的 $4$ 个参数即可。使用一个大小为 $10005 \times 4$ 的二维数组占用内存极小，完全满足轻量级空间限制的需求。

示例代码

#include <iostream>

// pos 数组用于存储地毯的信息
// pos[i][0], pos[i][1] 分别表示第 i 张地毯左下角的 x, y 坐标
// pos[i][2], pos[i][3] 分别表示第 i 张地毯在 x 轴和 y 轴方向的长度
int pos[10005][4];

int main() {
    int n;  // 地毯的总数 n
    std::cin >> n;

    // 依次读入每张地毯的信息，地毯编号从 1 到 n
    for (int i = 1; i <= n; i++) {
        std::cin >> pos[i][0] >> pos[i][1] >> pos[i][2] >> pos[i][3];
    }

    int x, y;  // 所求地面的点的坐标 (x, y)
    std::cin >> x >> y;

    int ans = -1;  // 记录所求的地毯的编号，如果没有被地毯覆盖则初始化输出 -1

    // 从最后铺设的（也就是最上面的）地毯开始倒序遍历
    // 只要找到第一个覆盖了点 (x, y) 的地毯，那就是覆盖该点的最上面的那张
    for (int i = n; i >= 1; i--) {
        // 判断点 (x, y) 是否在第 i 张地毯的覆盖范围内
        // 即 x 坐标在 [a, a + g] 之间，y 坐标在 [b, b + k] 之间
        if (x >= pos[i][0] && x <= pos[i][0] + pos[i][2] && y >= pos[i][1] &&
            y <= pos[i][1] + pos[i][3]) {
            ans = i;  // 记录答案（即对应的地毯编号）
            break;    // 找到了最上面的那张，直接退出循环
        }
    }

    // 输出结果，若没有地毯覆盖此处则会输出初始化时的 -1
    std::cout << ans << std::endl;

    return 0;
}

本文由coderli.com原创，按照CC BY-NC-SA 4.0 进行授权
所有代码已上传至Github：https://github.com/lihongzheshuai/yummy-code
“luogu-”系列题目可在 洛谷题库 在线评测。
“bcqm-”系列题目可在 编程启蒙题库 在线评测。

GESP/CSP认证交流QQ群： 688906745

GESP/CSP 认证学习微信公众号

最后更新于 2026年2月24日