洛谷 P1003 【铺地毯】

题解 P1003 【铺地毯】

题目描述

为了准备一个独特的颁奖典礼，组织者在会场的一片矩形区域（可看做是平面直角坐标系的第一象限）铺上一些矩形地毯。一共有 nn 张地毯，编号从 11 到nn。现在将这些地毯按照编号从小到大的顺序平行于坐标轴先后铺设，后铺的地毯覆盖在前面已经铺好的地毯之上。

地毯铺设完成后，组织者想知道覆盖地面某个点的最上面的那张地毯的编号。注意：在矩形地毯边界和四个顶点上的点也算被地毯覆盖。

输入输出格式

输入格式：

输入共n+2n+2行

第一行，一个整数nn，表示总共有nn张地毯

接下来的nn行中，第 i+1i+1行表示编号ii的地毯的信息，包含四个正整数a ,b ,g ,ka,b,g,k ，每两个整数之间用一个空格隔开，分别表示铺设地毯的左下角的坐标(a,b)(a,b)以及地毯在xx轴和yy轴方向的长度

第n+2n+2行包含两个正整数xx和yy，表示所求的地面的点的坐标(x,y)(x,y)

输出格式：

输出共11行，一个整数，表示所求的地毯的编号；若此处没有被地毯覆盖则输出-1−1

输入输出样例

输入样例#1：

输出样例#1：

输入样例#2：

输出样例#2：

首先,看50分的,范围100. 所以我们可以十分暴力的进行二维模拟

50分code

#include<iostream>
#include<stdio.h>
#include<string.h>
#include<algorithm>
#define maxn 500
using namespace std ;
int n ;int x , y , xx , yy ;
int f[maxn][maxn] ;
int main(){
    scanf("%d",&n) ;
    for(int i = 1 ; i <= n ; i ++){
        scanf("%d%d%d%d",&x,&y,&xx,&yy) ;
        for(int j = x ; j <= x + xx ; j ++ )
        for(int k = y ; k <= y + yy ; k ++ ){
            f[j][k] = i ;
        }
    }
    int a , b ;
    cin >> a >> b ;
    if(f[a][b]){
        cout << f[a][b] ;
    }else
    cout << -1 ;
    return 0 ;
}

但是,作为day1t1,的50分是远远不够的

于是,我们就可以进行一下别的思路

我们可以通过结构体的帮助来将其变为一维的

定义一个叫做carpet的struct 内有x1,x2,y1,y2,num五个变量分别表示x起点,x终点,y起点,y终点,以及地毯的编号

存好之后,吧编号从大到小排序,如果目标点在当前地毯中,就break掉

否则,就愉快的输出-1

ACcode

#include<iostream>
#include<string.h>
#include<stdio.h>
#include<algorithm>
using namespace std ;
struct dy{//说好的carpet呢!!!
    int x1,x2,y1,y2,num ;
}a[10010];
int n , m ;
int x , xx , y , yy ;
int cmp(dy x , dy y){
    return x.num > y.num ;
}
int main(){
    scanf("%d",&n) ;
    for(int i = 1 ; i <= n ; i ++){
        scanf("%d%d%d%d",&x,&y,&xx,&yy) ;
        a[i].x1 = x ;//x起点
        a[i].x2 = xx + x ;//x终点
        a[i].y1 = y ;//y起点
        a[i].y2 = yy + y;//y终点
        a[i].num = i ;//地毯序号
    }
    int aa , b ;
    scanf("%d%d",&aa,&b) ;
    sort(a+1,a+1+n,cmp) ;
    for(int i = 1 ; i <= n ; i ++){
        if(aa >= a[i].x1 && aa <= a[i].x2 && b >= a[i].y1 && b <= a[i].y2){//如果在当前地毯中,就输出当前地毯的编号
            printf("%d",a[i].num) ;
            return 0 ;//直接结束程序
        }
    }
    printf("%d",-1) ;//如果地毯都铺完了也没有找到,输出-1
    return 0 ;
}

完结散花!!!!

我的小链接:

https://www.luogu.org/blog/020321cosmos/

啥也没有hehe