模拟算法实战
枚举是模拟算法的基础,核心思想是将所有可能的情况罗列出来,再筛选出符合题目要求的那一个。虽然暴力枚举容易超时,但在数据范围允许时,它是解决问题的直接手段。优化枚举策略(如顺序、对象选择)往往是解题关键。
一、铺地毯
1. 题目描述
给定 n 张地毯,每张地毯覆盖矩形区域。查询某个坐标 (x, y) 被哪一张地毯覆盖。如果有多个,输出最后铺设的那一张;如果没有,输出 -1。

2. 思路分析
最直观的做法是遍历所有地毯判断是否覆盖。但题目要求的是最后一个覆盖该位置的地毯。如果正序枚举,必须遍历完所有地毯才能确定结果。更优的策略是逆序枚举:从最后一张地毯开始往前找,第一次遇到能覆盖 (x, y) 的地毯即为答案,找到即可返回,无需继续遍历。
3. 代码实现
#include <iostream>
using namespace std;
typedef long long LL;
const int N = 1e5 + 10;
LL a[N], b[N], g[N], k[N];
int n;
// 查找覆盖 (x, y) 的最后一张地毯编号
int find(int x, int y) {
for (int i = n; i >= 1; i--) {
// 判断当前地毯是否覆盖该点
if (x >= a[i] && y >= b[i] && x <= a[i] + g[i] && y <= b[i] + k[i]) {
return i;
}
}
return -1;
}
int main() {
cin >> n;
for (int i = ; i <= n; i++) {
cin >> a[i] >> b[i] >> g[i] >> k[i];
}
LL x, y;
cin >> x >> y;
cout << (x, y) << endl;
;
}




