这到题算是我“火线回归”后码的第一道题，病好了心情不错，发篇博客分享一下
目录：
·题目描述
·题目分析
·解题思路
·代码实现
·总结
·题目描述：
为了准备一场特殊的颁奖典礼，组织者在会场的一片矩形区域（可看做是平面直角坐标系的第一象限）铺上一些矩形地毯。一共有n张地毯，编号从1到n。现在将这些地毯按照编号从小到大的顺序平行于坐标轴先后铺设，后铺的地毯覆盖在前面已经铺好的地毯之上。地毯铺设完成后，组织者想知道覆盖地面某个点的最上面的那张地毯的编号。注意：在矩形地毯边界和四个顶点上的点也算被地毯覆盖。
·题目分析：
这道题看上去是一道很水很水的模拟题，一般人的第一思路就是套上三层循环，用一个二维数组模拟会场的每一块地板。不错， 我一开始也是这样想的，代码如下：
1 #include<cstdio> 2 #include<iostream> 3 4 using namespace std; 5 6 int n; 7 int a,b,g,k,xx,yy; 8 int ground[10010][10010]={-1};//赋值为-1的目的是如果没有被赋值，就可以直接输出-1，不用再判断了（其实就是懒） 9 10 int main() 11 { 12 scanf("%d",&n); 13 for(int i=1;i<=n;++i) 14 { 15 scanf("%d%d%d%d",&a,&b,&g,&k);//没有用数组，再每次输入的同时进行处理（用了数组之后的效果不如这样处理好） 16 for(int j=a;j<=a+g;++j) 17 for(int n=b;n<=b+k;++n)//又是两层循环，将每一块受到影响的（既需要更新的）地板的坐标进行枚举 18 ground[j][n]=i;//将这块地板附上最后一次赋值的值（模拟的是最上面的一块地毯） 19 } 20 scanf("%d%d",&xx,&yy); 21 printf("%d",ground[xx][yy]);//直接查找需要查找的地板最上面是那一块地毯 22 return 0; 23 }是的，这道题看上去很水，上面的代码看似完美无缺。但是结果是这样的：
是的，就是149.79s
所以，是什么导致了这种结果的发生呢？？？于是，我不要脸的点开了题解
原来，按照我的做法似是肯定会MLE的，因为这道题很坑，出题人的目的就是让我们将数据从前往后读入，再从后往前循环，从而求解（具体解题思路请继续往下看）
·解题思路：
根据上面的结论，我们可以找到一个更快、更优、更好的算法。
先将第2~n+1行的数据读入，存到一个二维数组中，然后从n~1枚举每一组数据，查看第一个包括需要查询的点的地毯。如果有，就直接输出这个地毯的编号，结束程序；如果没有，就输出“-1”，同样结束程序；
·代码实现：
说了这么多，没有代码怎么能行呢？？？
1 #include<cstdio> 2 #include<iostream> 3 4 using namespace std; 5 6 int shuju[10010][5];//定义一个“数据”数组，用来读入每一组数据 7 int n,xx,yy; 8 9 int main() 10 { 11 scanf("%d",&n); 12 for(int i=1;i<=n;++i) 13 for(int j=1;j<=4;++j) 14 scanf("%d",&shuju[i][j]);//读入数据ing 15 scanf("%d%d",&xx,&yy); 16 for(int i=n;i>=1;i--)//从n~1循环 17 { 18 if((shuju[i][1]<=xx)&&(shuju[i][3]+shuju[i][1]>=xx)&&(shuju[i][2]<=yy)&&(shuju[i][2]+shuju[i][4]>=yy))//判断要找的点是否再这个地毯内 19 { 20 printf("%d",i);//如果有，就输出该点的编号 21 return 0;//直接结束程序 22 } 23 } 24 printf("-1");//如果没有，就输出-1 25 return 0;//还是结束程序 26 }
·总结：
这道题还是很坑的，因为这道题不是单纯无脑的模拟，而是运用到了某种类似于“逆推还原”的思想，思路并不是很好想。所以在以后的解题过程当中，不要想当然，一定要仔细斟酌，然后就能AC啦！