洛谷 P1003 [NOIP 2011 提高组] 铺地毯（枚举法详解）c++

如果从前往后枚举地毯，假设枚举到一个地毯覆盖到所求的坐标，其实这个地毯是不是最终答案还不知道，因为我们要找的是最后覆盖的节点的地毯，所以从前往后找地毯，即使找到了一个地毯覆盖了题目中给的点，也不能确定它是不是最后一个，那我们从后往前枚举地毯的话，当我第一次找到一个地毯覆盖题目中的点，它一定是最终结果，这道题我们最优的枚举就是从后往前枚举。

drayzcc

521人浏览 · 2025-03-08 00:36:15

drayzcc · 2025-03-08 00:36:15 发布

枚举算法：

顾名思义，就是把所有情况全都罗列出来，然后找出符合题⽬要求的那⼀个。因此，枚举是⼀种纯暴⼒的算法。我们肯定做过类似的题目，在解决某个问题的时候是会把所有的情况一一罗列出来的，每罗列一种情况就判断一下是否符合题目要求，直到找到符合题目要求的那一个，这就是最终答案；⼀般情况下，枚举策略都是会超时的。此时要先根据题⽬的数据范围来判断暴⼒枚举是否可以通过。如果不⾏的话，就要⽤后⾯要学的各种算法来进⾏优化（⽐如⼆分，双指针，前缀和与差分等）。使⽤枚举策略时，重点思考枚举的对象（枚举什么），枚举的顺序（正序还是逆序），以及枚举的⽅式（普通枚举？递归枚举？⼆进制枚举）

题目链接： P1003 [NOIP 2011 提高组] 铺地毯 - 洛谷

1.题目分析

图示：（2，2）这个坐标被三个地毯覆盖，但我们要的是最上面的地毯，也就是3号地毯，输出的结果就是3；示例2查询的坐标是（4，5），可以发现并没有被这三个地毯所覆盖，所以输出-1

2.算法原理

解法:枚举所有的地毯，找出最后覆盖题目中点的那个地毯即可

从后往前枚举所有的地毯，判断是否覆盖题目中给的点

如何判断这个地毯会覆盖题目中给的点

假设X（x，y）坐标在地毯里面，a这个点必须要 ≤ x并且b要≤ y这个点才能跑到我的左上面，同理怎么跑到它的右下边，x要小于等于a+g，并且y要小于等于b+k，此时才能保证地毯覆盖到这个点，在边界的时候也算覆盖所以要取等，一会儿只要判断这四个条件同时成立，就说明我们这个地毯是能覆盖的

代码：

#include <iostream>
using namespace std;

const int N = 1e4 + 10;
int n; //读入地毯张数
int a[N], b[N], g[N], k[N]; //横坐标、纵坐标、x轴长度，y轴长度
int x, y; //需要被覆盖的点的坐标

int find()
{
    // 从后往前枚举
    for (int i = n; i >= 1; i--)
    {
        // 判断是否覆盖
        if (a[i] <= x && b[i] <= y && a[i] + g[i] >= x && b[i] + k[i] >= y)
        {
            return i;
        }
    }
    return -1;
}

int main()
{
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i] >> b[i] >> g[i] >> k[i];
    cin >> x >> y;

    //输出找到最后覆盖坐标点的地毯
    cout << find() << endl;

    return 0;
}