题解 | #铺地毯#
铺地毯
https://ac.nowcoder.com/acm/problem/16593
这道题其实可以用二维数组进行遍历把每张地毯的范围都涂一遍在数组上，最后再通过点的坐标找到数组上对应的值即为最终答案，
但是可以优化就是我们只关心这个点，只有地毯的范围包括在点里面，我们才把这个地毯的编号记录下来，这样时间复杂度只有o(n)，
再优化，因为他只要最后的，所以我们从n到1倒退，这样第一张符合的地毯就是最终答案，不要再找了。
```//方法二：
#include<bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
int n,x,y,num=-1;
int a[10005],b[10005],g[10005],k[10005];
int main(){
IOS;
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i]>>b[i]>>g[i]>>k[i];
}
cin>>x>>y;
for(int i=n;i>=1;i--){
if(x>=a[i]&&a[i]<=a[i]+g[i]&&y>=b[i]&&y<=b[i]+k[i]){
num=i;
break;
}
}
cout<<num;
return 0;
}
美团公司福利 3563人发布
查看10道真题和解析