洛谷刷题 P1003 [NOIP2011 提高组] 铺地毯

题目传送：P1003 [NOIP2011 提高组] 铺地毯

思路

该题主要考察模拟思想，可以用二维数组来模拟表示地面，每个坐标点记录其最上层地毯，然后每输入一张地毯数据就对地面相应坐标点进行修改，最后读取目标地点的状态，但是这样会超过题目要求的空间限制。所以，转换思维，用二维数组去记录所有地毯的信息，然后从后往前遍历，找到能覆盖到目标的地毯并输出

AC代码

#include<iostream>
using namespace std;const int MAX = 10001;
const int N = 4;
int carpet[MAX][N]; // 存储地毯信息
int main()
{// 输入int n,target_x,target_y;cin >> n;for (int i = 0; i < n; i++){for (int j = 0; j < N; j++){cin >> carpet[i][j];}}// for (int i = 0; i < n; i++)// {//     for (int j = 0; j < N; j++)//     {//         cout << carpet[i][j] << " ";//     }//     cout << endl;// }cin >> target_x >> target_y; // 目标位置int a,b,g,k;                 // 记录地毯信息int target_carpet = -1;      // 目标地毯// 从后往前遍历找到目标地毯for (int i = n-1; i >=0; i--){a = carpet[i][0];b = carpet[i][1];g = carpet[i][2];k = carpet[i][3];if (a <= target_x && target_x <= a + g && b <= target_y && target_y <= b+k){target_carpet = i + 1; // 注意地毯编号与下标对应关系break;} }cout << target_carpet; return 0;
}