NOIP 2011 提高组 洛谷P1003 地毯覆盖的逆向思维解法与分析

一、问题描述

在平面直角坐标系上，按顺序铺放n张矩形地毯，给出每张地毯的左下角坐标(a,b)、长度g和高度k。最后询问某个点(x,y)最上面覆盖的是第几张地毯。如果没有地毯覆盖该点，输出-1。

二、逆向思维解法

直接从最后一张地毯开始反向检查，找到第一个覆盖目标点的地毯即可。这种方法避免了存储所有地毯信息，时间和空间效率都很高。

三、C++代码实现

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

struct Carpet {
    int 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;
    
    // 从最后一张地毯开始反向检查
    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;
}

四、算法详解

1. 数据结构设计

使用结构体存储每张地毯的参数：

• a, b: 左下角坐标

• g: 地毯长度（x轴方向）

• k: 地毯高度（y轴方向）

2. 关键算法步骤

1. 读取所有地毯数据

2. 从最后一张地毯开始反向遍历

3. 检查目标点是否在当前地毯覆盖范围内

4. 找到第一个满足条件的地毯立即返回结果

3. 复杂度分析

• 时间复杂度：O(n)

• 空间复杂度：O(n)存储地毯信息

五、优化与扩展

1. 内存优化：可以边读入边处理，不需要存储全部地毯

2. 多查询优化：建立空间索引结构加速查询

3. 动态更新：支持插入和删除地毯操作

六、常见错误

1. 地毯编号从1开始但数组从0开始

2. 边界条件处理（地毯刚好覆盖边界点）

3. 忘记处理无覆盖的情况（输出-1）