p1003 铺地毯,枚举

记录每个地毯情况,然后因为只问一点情况,所以从后循环查找
注意该题目:如果模拟整个客厅——(1e5)2直接爆掉,但只有一次询问,地毯1e4,所以遍历每个地毯看是否符合
输入每个地毯的情况
输入要查找的点x,y
for (i:从后往前遍历){
    if (x和y都在i地毯区域)输出i;break;
    if (i==1,最后一块地毯都没break)输出-1; 
}
代码
#include <bits/stdc++.h>

using namespace std;

const int N=10005;
int n,x,y;
int a[N],b[N],g[N],k[N];

int main(int argc, char** argv) {
	cin>>n;
	for(int i=1;i<=n;i++){
		scanf("%d%d%d%d",&a[i],&b[i],&g[i],&k[i]);
	}
	cin>>x>>y;
	for(int i=n;i>=1;i--){
		if(a[i]<=x&&a[i]+g[i]>=x&&b[i]<=y&&b[i]+k[i]>=y){
			cout<<i<<endl;break;
		}
		if(i==1) cout<<-1<<endl;
	}
	return 0;
}


一开始想把整个客厅模拟,直接爆存储
for (i:1~n){
    输入地毯情况
    for (j:地毯x坐标)
        for (l:地毯y坐标)
            修改地毯对应客厅的值ground[j][l](此处有(1e5)^2时间复杂度直接爆掉)
}
输入查询点x,y
输出x,y处客厅对应情况


全部评论

相关推荐

不要停下啊:大二打开牛客,你有机会开卷了,卷起来,去找课程学习,在牛客上看看大家面试笔试都需要会什么,岗位有什么需求就去学什么,努力的人就一定会有收获,这句话从来都经得起考验,像我现在大三了啥也不会,被迫强行考研,炼狱难度开局,啥也不会,找工作没希望了,考研有丝丝机会
点赞 评论 收藏
分享
门口唉提是地铁杀:之前b站被一个游戏demo深深的吸引了。看up主页发现是个初创公司,而且还在招人,也是一天60。二面的时候要我做一个登录验证和传输文件两个微服务,做完要我推到github仓库,还要我加上jaeger和一堆运维工具做性能测试并且面试的时候投屏演示。我傻乎乎的做完以后人家跟我说一句现在暂时不招人,1分钱没拿到全是白干
你的秋招第一场笔试是哪家
点赞 评论 收藏
分享
不愿透露姓名的神秘牛友
07-02 15:39
希望奇迹发生的布莱克...:真的是 现在卷实习就是没苦硬吃
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务