P4712 铺地毯（基础）

解题思路

会场里铺了 n 张地毯，编号从 1 到 n，按照编号从小到大的顺序先后铺设，后铺的地毯会盖住先铺的地毯。现在要问某个点 (x,y) 最上面盖着的是哪张地毯，如果这个点没有被任何地毯盖住，就输出 -1。

生活类比：这就像在桌面上铺一层层桌布，每次新铺的桌布总是盖在最上面。想知道某个位置最上面是什么桌布，只需要从最后铺的那张桌布开始，一张一张往前翻，翻到的第一张能盖住这个位置的桌布就是答案。

所以算法就是从编号 n 开始往前检查到编号 1，第一个能盖住点 (x,y) 的地毯就是最上面那张，直接输出它的编号并结束程序。

怎么判断点在地毯上？地毯 i 的左下角坐标是 (a,b)，向右延伸 g，向上延伸 k。也就是说，这块地毯覆盖了 x 从 a 到 a+g、y 从 b 到 b+k 的整个矩形。点 (x,y) 被这块地毯盖住，当且仅当同时满足：

• a ≤ x ≤ a+g
• b ≤ y ≤ b+k

题目明确说：在矩形边界上和四个顶点上的点也算被地毯覆盖，所以判断时一定要用 ≤ 而不是 <，边界情况不能漏。

如果从编号 n 一直数到 1 都没有找到能盖住这个点的地毯，说明这个点没有被覆盖，输出 -1。

参考代码

// 铺地毯：从最后一张地毯往前找，判断点是否被覆盖
#include <iostream>
using namespace std;
int a[10005], b[10005], g[10005], k[10005];
int main() {
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i] >> b[i] >> g[i] >> k[i];
    int x, y;
    cin >> x >> y;
    // 后铺的地毯在上面，从编号最大的往前找
    for (int i = n; i >= 1; i--) {
        if (x >= a[i] && x <= a[i] + g[i] && y >= b[i] && y <= b[i] + k[i]) {
            cout << i << endl;
            return 0;
        }
    }
    cout << -1 << endl;
    return 0;
}

复杂度分析

程序从最后一张地毯开始往前检查，最多检查 n 张地毯，每张地毯只需要做几次数值比较，所以时间复杂度是 O(n)。n 最大是 10000，最坏情况下也只需要一万次比较，瞬间就能出结果。

空间方面，用四个长度 10005 的数组分别存每张地毯的 a、b、g、k 四个参数，空间复杂度 O(n)，完全在允许范围内。