枚举——NOIP2011 铺地毯

链接：https://ac.nowcoder.com/acm/problem/16593

为了准备一个独特的颁奖典礼，组织者在会场的一片矩形区域（可看做是平面直角坐标系的第一象限）铺上一些矩形地毯。一共有n张地毯，编号从1到n。现在将这些地毯按照编号从小到大的顺序平行于坐标轴先后铺设，后铺的地毯覆盖在前面已经铺好的地毯之上。地毯铺设完成后，组织者想知道覆盖地面某个点的最上面的那张地毯的编号。注意：在矩形地毯边界和四个顶点上的点也算被地毯覆盖。

枚举优化思路：减少枚举次数——1.选择合适的枚举对象。2.选择合适的枚举方向。3.选择合适的数据维护方法；

题解：

using namespace std;

const int N = 1e4 + 10;
long long a[N], b[N], g[N], h[N];
int x, y;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n;
	cin >> n;
	int ans = -1;
	for (int i = 1; i <= n; i++) {
		cin >> a[i] >> b[i] >> g[i] >> h[i];
	}
	cin >> x >> y;
	for (int i = n; i >= 1; i--) {
		if (x >= a[i] && x <= a[i] + g[i] && y >= b[i] && y <= b[i] + h[i]) {
			ans = i;
			break;
		}
	}
	cout << ans << endl;
	return 0;
}

自己一开始想的是模拟方法，但是在这么大数据的情况下模拟显然是不行的。所以选择了这个枚举方法，将每个地毯先保存下来，我们要找的只是那个点最后所在的地毯，所以我们可以采用倒叙，只要找到那个点就输出所在地毯就可以了。