P1003 铺地毯

P1003 铺地毯

解题思路：

一开始想着开二维数组，发现数组不能开那么大，而且二维数组没有能记录直接得出是第几块地毯最后覆盖的。
所以定义了一个名为地毯的结构体，再开个结构体数组，用来保存每块地毯的信息。
然后依次遍历结构体数组，找到最后在坐标上的地毯。

ACcode:

#include<iostream> 
#include<cstdio>
using namespace std;

typedef struct 
{
	int a1, b1;
	int a2, b2;
	int g, k;
}ditan;

ditan ditans[10005];

int main()
{
	int n;	scanf("%d", &n);
	for(int i=1; i<=n; i++)
	{
		scanf("%d %d %d %d", &ditans[i].a1, &ditans[i].b1, &ditans[i].g, &ditans[i].k);
		ditans[i].a2 = ditans[i].a1 + ditans[i].g;
		ditans[i].b2 = ditans[i].b1 + ditans[i].k;
	}
	int x, y;
	scanf("%d %d", &x, &y);
	int arr = -1;
	for(int i=1; i<=n; i++)
	{
		if(ditans[i].a1<=x && ditans[i].a2>=x)
		{
			if(ditans[i].b1<=y && ditans[i].b2>=y)
			{
				if(arr < i)
				{
					arr = i;
				}
			}
		}
	}
	printf("%d", arr);
	return 0;
	
}

结果：

解题用时:

改进地方：

可以直接从最后块地毯往前遍历，这样找到的第一块地毯的编号就是答案。

ACcode++

#include<iostream> 
#include<cstdio>
using namespace std;

typedef struct 					//名为地毯的结构体 
{
	int a1, b1;					//左下角坐标 
	int a2, b2;					//右上角坐标 
}ditan;

ditan ditans[10005];			//用来保存每一块的地毯的结构体数组 

int main()
{
	int n;	scanf("%d", &n); 	//输入地毯数量 
	
	for(int i=1; i<=n; i++)		//输入每块地毯信息 
	{
		int g, k;
		scanf("%d %d %d %d", &ditans[i].a1, &ditans[i].b1, &g, &k);
		ditans[i].a2 = ditans[i].a1 + g;
		ditans[i].b2 = ditans[i].b1 + k;
	}
	
	int x, y;
	scanf("%d %d", &x, &y);		//输入要找的坐标 

	for(int i=n; i>=1; i--)		//遍历寻找 
	{
		if(ditans[i].a1<=x && ditans[i].a2>=x)
		{
			if(ditans[i].b1<=y && ditans[i].b2>=y)
			{
				printf("%d", i);
				return 0;
			}
		}
	}
	
	printf("-1");
	return 0;
}

结果：

还慢了一丢丢。。。不过因为没有保存地毯长度和宽度，所以内存消耗变小了。

心得：

这道题有模拟的标签，我感觉，所谓模拟，就要按照题目的描述模拟提炼出一个模型，多数用结构体实现，运用来解题的时候注意边界范围就好了。

END