[NOIP 2011 提高组] 铺地毯

题意

有 n 张矩形地毯按编号从小到大依次铺在平面上。
给定一个查询点 (x,y)，要求输出覆盖这个点的最上面那张地毯编号；如果没有地毯覆盖它，输出 -1。

思路

先看一个可以直接验证想法的朴素解：

按铺设顺序从前往后扫一遍，凡是覆盖查询点的地毯都把答案更新成当前编号。

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38// brute.cpp：小数据暴力解，用来帮助理解题意并辅助对拍。
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 10005;

int n;
int a[MAXN], b[MAXN], g[MAXN], k[MAXN];
int x, y;

void solve() {
    int ans = -1;

    // 按铺设顺序检查，后面覆盖到前面时直接更新答案。
    for (int i = 1; i <= n; i++) {
        if (a[i] <= x && x <= a[i] + g[i] &&
            b[i] <= y && y <= b[i] + k[i]) {
            ans = i;
        }
    }

    cout << ans << '\n';
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i] >> b[i] >> g[i] >> k[i];
    }
    cin >> x >> y;

    solve();

    return 0;
}

这个做法已经能做出来，但还有一个更贴合题意的观察：

后铺的地毯一定在前铺的地毯上面。

所以如果一个点被多张地毯覆盖，真正的答案一定是编号最大的那一张。
于是我们完全可以反过来做：

从第 n 张地毯开始往前找
第一张覆盖查询点的地毯，就是最上面的地毯

这样一旦找到就可以立刻结束。

判断一张地毯是否覆盖查询点时，要注意边界和顶点也算覆盖，所以比较要写成闭区间判断。

代码

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38#include <bits/stdc++.h>
using namespace std;

const int MAXN = 10005;

int n;
int a[MAXN], b[MAXN], g[MAXN], k[MAXN];
int x, y;

int cover(int id, int px, int py) {
    return a[id] <= px && px <= a[id] + g[id] &&
           b[id] <= py && py <= b[id] + k[id];
}

void solve() {
    for (int i = n; i >= 1; i--) {
        if (cover(i, x, y)) {
            cout << i << '\n';
            return;
        }
    }
    cout << -1 << '\n';
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i] >> b[i] >> g[i] >> k[i];
    }
    cin >> x >> y;

    solve();

    return 0;
}

复杂度

时间复杂度是 $O(n)$ ，空间复杂度是 $O(n)$ 。

总结

这题的关键不在矩形本身，而在铺设顺序。

抓住“后铺的在上面”这句话，直接逆序枚举，就能把答案很快找出来。

[NOIP 2011 提高组] 铺地毯

目录

题意

思路

代码

复杂度

总结