02 洛谷 P1003 铺地毯

题目链接

这题也很简单，但是思路必须要能转过来，不能死脑筋。

我一共提交了两次，第二次提交正确。

1. 第一次提交错误信息： 图片.png
   第一次提交代码: 图片.png

RE（run time error） 通常是表示使用了不合法的内存，很可能是数组越界等导致程序崩溃。

看看题目数据范围: 图片.png
对于100%的数据。是可能达到10^5的。

而我在第一次做题的过程中，使用的是完全模拟的方法，需要用二维数组来模拟地毯的铺设：第一张地毯铺上去就给所有范围的二维数组赋值1，第二张……赋值2， 以此类推。
那么就需要我们的二维数组有足够大来模拟所有的数据。但是我测试过，我们本地的编译器在申请超过20000×20000大小的数组后就会编译出错了（洛谷支持的更小），然后我不得不把数组开到满足50%数据的大小：100，我开了个1000×1000的数组，那么当然对于剩下的50%的数据超过了数组的索引范围自然会产生RE的错误了。

2. 知道了数组大小的限制后，我开始思考正确的方法：其实根本不需要完全模拟整个过程，只需要保存下来每个输入数据的信息，然后倒着去判断所给数据是否在输入数据的范围内即可。而保存所有输入数据的信息只需要使用二维数组即可：最大 图片.png
   

   显然已经满足了题目要求。
   

   再次提交,已经完全正确 图片.png

代码：

#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
typedef long long ll;

int nums[10002][5];

void solve(int n, int x, int y) {
    for(int i = n - 1; i >= 0; i--) {
        if(x >= nums[i][0] && x <= nums[i][0] + nums[i][2] &&
           y >= nums[i][1] && y <= nums[i][1] + nums[i][3]) {
            printf("%d", i + 1);
            return;
        }
    }
    printf("-1");
}

int main(int argc, char const *argv[])
{
    int n, x, y;
    scanf("%d", &n);
    for(int i = 0; i < n; i++) {
        scanf("%d%d%d%d", &nums[i][0], &nums[i][1], &nums[i][2], &nums[i][3]);
    }
    scanf("%d%d", &x, &y);
    solve(n, x, y);

    return 0;
}