题目
分析
第一种做法
一开始想的是模拟做法:声明一个二维数组,输入数据说哪里有地毯就给哪里替换成相应的地毯编号。
如输入数据一:
第一步:
第二步:
第三步:
但是我们看数据量: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;
}