题解 | 铺地毯

解题思路

因为地毯是按编号从小到大依次铺设的，后铺的会盖住先铺的。

我们要找的是覆盖点 (o, p) 的最上面那张地毯，也就是编号最大的那张。

解题步骤

1. 读入 n，然后读入每张地毯的参数 (a, b, x, y)，其中 (a, b) 是左下角，x 和 y 分别是沿 x 轴和 y 轴的长度。
2. 读入目标点 (o, p)。
3. 从第一张地毯开始往后遍历，判断点是否在当前地毯范围内： 条件：o >= a 且 o <= a + x 且 p >= b 且 p <= b + y。
4. 如果满足条件，就更新答案为当前地毯编号。

复杂度

• 时间：O(n)，只需遍历一次所有地毯。
• 空间：O(1)，只记录当前地毯参数，不需要存储全部。

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

struct paper{
    int a, b, x, y;
    int num;
};

int main() {
    int n;cin>>n;
    vector<paper> arr(n);
    int ans = 0;
    for(int i = 0;i < n;++i){
        cin>>arr[i].a >> arr[i].b>>arr[i].x>>arr[i].y;
        arr[i].num = i + 1;
    }    
    int o, p;cin>>o>>p;
    for(int i = 0;i < n;++i){
        if(o >= arr[i].a && o <= arr[i].a + arr[i].x &&
            p >= arr[i].b && p <= arr[i].b + arr[i].y
        ){
            ans = arr[i].num;
        }
    }
    cout<<ans<<endl;
}
// 64 位输出请用 printf("%lld")