题解-1016-[NOIP2011]铺地毯

解题思路

贪心。
用一个结构体数组来存每块地毯的左下右上坐标，判点在不在区域内可以用逆否命题（即判断的时候跳过超出区域边界值的点）。因为地毯是按输入的顺序铺开的，题目要求输出最上面的地毯那么只需要倒序遍历，第一个没被跳过的地毯就是覆盖在当前点最上层的地毯，输出编号 $breakbreak$ 掉循环就好。时间复杂度 $O(n)O(n)$ 。

通过代码

#include<bits/stdc++.h>
using namespace std;
int n;
struct ty
{
    int xl, yl, xr, yr;
}a[10010];
int main()
{
    cin >> n;
    for (int i = 1; i <=n ; i++)
    {
        int g, k;
        cin >> a[i].xl >> a[i].yl;
        cin >> g >> k;
        a[i].xr = g + a[i].xl;
        a[i].yr = k + a[i].yl;
    }
    int x, y;
    cin >> x >> y;
    for (int i = n; i >= 1; i--)
    {
        if (x < a[i].xl || x > a[i].xr || y < a[i].yl || y > a[i].yr)
            continue;
        else {
            cout << i << endl;
            break;
        }
    }
    return 0;
}