JZTXT

P1003 [NOIP2011 提高组] 铺地毯

发布时间 2023-10-07 22:35:30作者: MLE_Automation

第一思路：

开一个N*N的数组，每次都扫一遍地毯范围并标记编号

然后你会发现：喜提MLE

为什么呢？

我们来看看数据范围
0 ≤ n ≤ 1e4
n的范围是1e4，数组总大小为1e16，大约需要4000TB的内存空间

服务器也不带这么玩的

正解：

将地毯信息用结构体存储

struct node{
	int x1, y1, x2, y2;//x1 y1是左下角，x2 y2是右上角
}N[10005];

只有1次询问，可以从后向前扫描所有地毯，检查点(x, y)是否在地毯内部

for (int i = n; i >= 1; i--){//要找最上面地毯的编号，所以反着扫
	if(x >= N[i].x1 && x <= N[i].x2 && y >= N[i].y1 && y <= N[i].y2){
		ans = i;//从上面找到第一个覆盖到的地毯的编号，即为答案
		break;//找到答案之后直接跳出，输出答案
	}
}

完整die码

#include <bits/stdc++.h>

using namespace std;

int n, x, y, ans = -1;//ans初始值为-1，表示没有覆盖
int a, b, g, k;

struct node{
	int x1, y1, x2, y2;//x1 y1是左下角，x2 y2是右上角
}N[10005];

int main(){
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);

	cin >> n;
	for (int i = 1; i <= n; i++){
		cin >> a >> b >> g >> k;
		N[i] = {a, b, a + g - 1, b + k - 1};//存储第i个地毯左下角和右上角的坐标
	}
	cin >> x >> y;
	for (int i = n; i >= 1; i--){//要找最上面地毯的编号，所以反着扫
		if(x >= N[i].x1 && x <= N[i].x2 && y >= N[i].y1 && y <= N[i].y2){
			ans = i;//从上面找到第一个覆盖到的地毯的编号，即为答案
			break;//找到答案之后直接跳出，输出答案
		}
	}
    //如果一直没有跳出，代表没有地毯覆盖

	cout << ans << '\n';

	return 0;
}