算法学习记录:[NOIP2011]铺地毯

发布时间 2023-05-20 10:35:18作者: 想个昵称好难ABCD

题目链接:

  https://ac.nowcoder.com/acm/contest/20960/1016

解题思路:

最直观的方法,因为编号大的地毯一定更靠后,所以直接用编号进行标记。

时间复杂度分析:

该代码时间复杂度为\(O(N^2)\),有\((10^5)^2\),评测oj每1秒能接受的时间复杂度为:\([10^8,10^9]\)
所以下代码一定TLE。

TLE代码

#include <iostream>

using namespace std;

// 编号大的一定在上面,所以依次暴力枚举所有地毯

const int N = 10005;

int n, cnt = 1, ans;
int x, y, a, b;		// (x,y), 分别为x,y方向的长度
int m[N][N];

int main()
{
	cin >> n;
	while (n -- )
	{
		cin >> x >> y >> a >> b;
		for (int i = x; i <= x + a; ++ i)
			for (int j = y; j <= y + b; ++ j)
				m[i][j] = cnt;
		cnt ++ ;
	}

	cin >> x >> y;
	cout << m[x][y];

	return 0;
}