NOIP提高组2011铺地毯题（洛谷P1003）解析与代码实现：反向遍历求解覆盖问题

一、题目解读

“铺地毯”是2011年NOIP提高组的经典题目（对应洛谷P1003）。题目描述了一个平面上存在多张矩形地毯，每张地毯有左下角坐标(a,b)和宽高(g,k)，给定目标点(x,y)，需判断覆盖该点的最上层地毯编号（若未被覆盖则输出-1）。问题本质是二维区间查询，考验对坐标范围与覆盖顺序的理解。

二、解题思路

采用“反向遍历+范围检查”的策略：

1. 按输入顺序存储地毯数据，但从最后一张地毯开始检查（即逆序遍历）；

2. 利用矩形范围判断点(x,y)是否被当前地毯覆盖（通过四个边界条件）；

3. 由于地毯按铺设顺序存储，第一个覆盖目标点的地毯即为最上层，直接退出循环。

该思路巧妙利用“后铺设覆盖前铺设”的特性，避免复杂排序或数据结构，时间复杂度O(n)。

三、解题步骤

4. 数据读取：使用vector存储n张地毯的(a,b,g,k)参数；

5. 目标点处理：读入查询点(x,y)，初始化结果result为-1；

6. 反向查找：从n-1到0遍历地毯，若当前地毯覆盖(x,y)，更新result并break；

7. 输出结果：直接输出result，完成解题。

四、代码与注释

#include <iostream>
#include <vector>
using namespace std;

struct Carpet {
    int a, b, g, k; // 左下角(a,b) + 宽g、高k
};

int main() {
    int n;
    cin >> n;          // 输入地毯数量
    vector<Carpet> carpets(n);
    
    // 读取所有地毯数据
    for (int i = 0; i < n; ++i) {
        cin >> carpets[i].a >> carpets[i].b >> carpets[i].g >> carpets[i].k;
    }
    
    int x, y;
    cin >> x >> y;     // 目标点坐标
    int result = -1;   // 初始化结果（未覆盖时为-1）
    
    // 从最后一张地毯开始反向检查
    for (int i = n - 1; i >= 0; --i) {
        // 检查点(x,y)是否在当前地毯范围内
        if (x >= carpets[i].a && x <= carpets[i].a + carpets[i].g &&
            y >= carpets[i].b && y <= carpets[i].b + carpets[i].k) {
            result = i + 1; // 地毯编号从1开始，更新结果并退出
            break;
        }
    }
    
    cout << result << endl;
    return 0;
}

五、总结

该代码通过反向遍历简化了覆盖顺序的判断，无需预处理或高级数据结构，展现了算法设计中“利用输入顺序特性”的巧妙思维。对于区间查询类问题，若数据本身隐含顺序规律，反向处理常能降低复杂度。同时，清晰的边界检查与简洁的循环结构是高效解题的关键。

参考：2011年NOIP提高组铺地毯题解