枚举
这个题目有点意思,首先我们不能一个一个去覆盖,万一枚举的这个点正好所有的地毯都覆盖它,那么就全部需要遍历一次,,,,,,所以那该怎办呢.......正难则反,我们就反向遍历一旦遇到改点被当前毛毯覆盖就输出来然后直接return就行,这将大大减少代码的运行量。
因为题目已知毛毯的左下角,也就是最小的边界,如果需要访问的点小于毛毯的最小值,那直接就跳过就行,因为继续遍历下去也不会有结果。
这里可以定义结构体去存储数据,也可以定义四个一维数组去存贮数据,个人建议定义一个结构体去存储所有的数据会方便许多。
#include <bits/stdc++.h> using namespace std; const int maxn = 1e6 + 10; struct node { int x, y, a, b; } w[maxn]; int main() { int n, xx, yy; while (~scanf("%d", &n)) { for (int i = 1; i <= n; ++i) scanf("%d%d%d%d", &w[i].x, &w[i].y, &w[i].a, &w[i].b); scanf("%d%d", &xx, &yy); for (int i = n; i >= 1; --i) { if (xx < w[i].x || yy < w[i].y) continue; if (xx - w[i].x <= w[i].a && yy - w[i].y <= w[i].b) { printf("%d\n", i); return 0; } } } }