1 条题解

  • 11
    @ 2023-5-2 15:25:33

    在阅读题解之前,先给各位 dalao 安利一下我的个人博客呗~感兴趣的 dalao 也可以在我的博客上查看,看完了别忘了点个赞哟~

    好了,说正事:

    说实话,第一眼看到这道题,觉得天呐,好复杂,但是如果你真正读懂了这道题,会觉得题目根本就是在坑你,哪有那么复杂

    先说思路,其实这道题的数据非常水,仔细阅读会发现,nn 的最大值竟然只有小小的一万,没错,这不就是枚举吗?

    我们先输入各组数据,再依次枚举,只用看看这一个点是否有被地毯覆盖就行了。

    但是,

    注意!!!

    一定要从大到小进行枚举,因为题目是让输出盖在此点上的最大的地毯编号。

    然后就……没什么好讲的了

    又到了最欢乐的代码时间。

    #include<bits/stdc++.h>
    using namespace std;
    const int max_n=10005;
    long long int n,j[max_n],k[max_n],a[max_n],b[max_n],x,y;
    void z(){
    	//freopen("carpet.in","r",stdin);					 //比赛的时候记得加这两句 
    	//freopen("carpet.out","w",stdout);
    	scanf("%lld",&n);
    	for(int i=1;i<=n;i++)scanf("%lld%lld%lld%lld",&j[i],&k[i],&a[i],&b[i]);
    	scanf("%lld%lld",&x,&y);
    	for(int i=n;i>=1;i--){           					 //从大到小依次枚举每块地毯 
    		if(x<=j[i]+a[i]&&x>=j[i]&&y<=k[i]+b[i]&&y>=k[i]){//判断目标点是否被覆盖 
    			printf("%d",i);								 //输出编号				 
    			return;										 //返回主函数 
    		}
    	}													 //跳出循环则代表目标点没有被覆盖 
    	printf("-1");										  
    	return;
    }
    int main(){
    	z();
    	return 0; 											 //记得加这句,不然比赛的时候会错!!! 
    }
    

    该代码时间复杂度为 O(n)O(n)

    代码已 AC。

    请放心食用

    相见就是缘分呀~

    如果你看到了,不妨留下个赞再走呗,感谢观看~

    886~

    • 1

    信息

    ID
    678
    时间
    1000ms
    内存
    16MiB
    难度
    10
    标签
    递交数
    7
    已通过
    4
    上传者