[C++知识库]【洛谷题解】P1003 [NOIP2011 提高组] 铺地毯 题解

题目传送门

提前上代码:

#include<bits/stdc++.h>

using namespace std;

int a[100005],b[100005],g[100005],k[100005];

int main()
{
	int n,t = -1,x,y;
	cin>>n;
	for(int i = 0;i < n;i++)
		cin>>a[i]>>b[i]>>g[i]>>k[i];
	cin>>x>>y;
	for(int i = n - 1;i >= 0;i--)
	{
		if(a[i] <= x && b[i] <= y && a[i] + g[i] >= x && b[i] + k[i] >= y)
		{
			t = i + 1;
			break;
		}
	}
	cout<<t;
	return 0;
}

提前说一下，我以后都会使用#include<bits/stdc++.h>来写代码，所以不习惯的可以写平常的头文件，如include<iostream>、#include<cstring>、#include<ctime>等。
好，开始看代码。
头文件说过了，就不再说。
关于变量，我直接将t设为-1，就不用再使用flag等骚操作去辨认有没有去修改值。
输入就按照格式来。
接着看一看数据范围:

对于 30% 的数据，有 n≤2。
对于 50% 的数据，0≤a,b,g,k≤100。
对于 100% 的数据，有 0≤n≤10⁴,0≤a,b,g,k≤10⁵ 。

好，既然n没到10⁸,那么就可以直接写O(n)的代码。
直接for循环。
里面就是判断是否有叠在这个点上，有k就直接等于i，退出。
如果像我这么写，就要注意for的范围，不能取到n，也就是[0,n)。
然后就可以愉快的提交啦!
有此为证