<span>洛谷 P1003 铺地毯</span>

题目

题目传送门

分析

第一种做法

一开始想的是模拟做法：声明一个二维数组，输入数据说哪里有地毯就给哪里替换成相应的地毯编号。
如输入数据一：
第一步：

第二步：

第三步：

但是我们看数据量：10000个地毯，每个地毯最大100000 * 100000，按照模拟做法，最多要循环10000 * 100000 * 100000次。
很明显，模拟不可行。

第二种做法

数据在最后给了要查看的位置的xy坐标，那么我们可以只查看那个位置被哪些地毯覆盖就行了。
而且我们可以发现，只需要找出逆着的第一个就行了，因为后面的肯定会覆盖前面的。
最不利也就是循环10000次。
所以可以使用这种方法。

AC代码奉上：

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

int a[10010] = {0}, b[10010] = {0}, g[10010] = {0}, k[10010] = {0}, s[10010] = {0};//s数组标记地毯序号
int main()
{
	int n = 0, x = 0, y = 0, f = 1;//f标记是否有解
	cin >> n;
	for(int i = 1; i <= n; i++)   
	{
		cin >> a[i] >> b[i] >> g[i] >> k[i];   
		s[i] = i;
	}
	
	cin >> x >> y;
	
	for(int i = n; i >= 1; i--)
	{
		if(x >= a[i] && x <= a[i] + g[i] && y >= b[i] && y <= b[i] + k[i])
		{
			cout << s[i];
                        f = 0;//逆序找，如果发现有解，把f标记为0，输出并退出循环
			break;
		}        
	}
	
	if(f == 1)
	{
		cout << "-1";//如果无解就输出-1
	}
	 
	return 0;   
}