【题解】洛谷 P1003 [NOIP2011 提高组] 铺地毯

原题链接

解题思路

如果直接按照题意开一个二维数组来模拟每个点最上面的地毯编号，会发现所占空间最坏情况下约为 (2*10⁵)²*4B=4*10¹⁰*4B=1.6*10¹¹B≈149GB，程序完全无法运行。

但实际上没有必要将每一个点的信息记录下来，只需要记录每一块地毯能覆盖哪些点，再依次判断哪那些地毯可以覆盖所求的点，输出最后一个符合此要求的地毯编号就可以了。时间复杂度 O(n)，可以通过此题。

注意：如果把所有的地毯都找完了还是没发现能覆盖所求的点的地毯，就要输出-1。

代码实现

#include<bits/stdc++.h>
using namespace std;
const int N = 10005;
int n, x, y;
struct node {
	int x1, y1;
	int x2, y2;
} m[N];
int main() {
	cin >> n;
	for (int i = 1; i <= n; i ++) {
		int a, b, g, k;
		cin >> a >> b >> g >> k;
		m[i].x1 = a, m[i].y1 = b;
		m[i].x2 = a + g, m[i].y2 = b + k;
	}
	cin >> x >> y;
	for (int i = n; i; i --)
		if (x >= m[i].x1 && x <= m[i].x2 && y >= m[i].y1 && y <= m[i].y2) {
			cout << i << endl;
			return 0;
		}
	puts("-1");
	return 0;
}