首页 > 试题广场 >

病毒扩散

[编程题]病毒扩散
  • 热度指数:762 时间限制:C/C++ 2秒,其他语言4秒 空间限制:C/C++ 256M,其他语言512M
  • 算法知识视频讲解
牛牛刚刚得知牛牛所在的街道上有一个人得了新型冠状病毒!!!由于新型冠状病毒传染力很强,所以,只要在被传染的人的活动范围内活动都有可能被感染!现根据大数据可以得知,初始患病人在整个街道人群中的序号Pid和每个人在街道上的活动区域Pos。因为情况紧急,所以牛牛想请你帮忙快速计算下究竟最坏情况下会有多少人感染上冠状病毒?


示例1

输入

1,[(1,2),(2,3)]

输出

2

说明

最坏情况下两个人都被感染
示例2

输入

1,[(1,2),(3,4)]

输出

1

说明

最坏情况下只有一个人被感染

备注:
人的编号从0开始
个人的活动范围为[Pos[i].x,Pos[i].y];
<

头像 未来0116
发表于 2021-08-12 21:22:54
一.题目描述NC539病毒扩撒牛牛刚刚得知牛牛所在的街道上有一个人得了新型冠状病毒!!!由于新型冠状病毒传染力很强,所以,只要在被传染的人的活动范围内活动都有可能被感染!现根据大数据可以得知,初始患病人在整个街道人群中的序号Pid和每个人在街道上的活动区域Pos。因为情况紧急,所以牛牛想请你帮忙快速 展开全文
头像 认认真真coding
发表于 2021-08-03 19:53:51
题目描述牛牛刚刚得知牛牛所在的街道上有一个人得了新型冠状病毒!!!由于新型冠状病毒传染力很强,所以,只要在被传染的人的活动范围内活动都有可能被感染!现根据大数据可以得知,初始患病人在整个街道人群中的序号Pid和每个人在街道上的活动区域Pos。因为情况紧急,所以牛牛想请你帮忙快速计算下究竟最坏情况下会 展开全文
头像 QSheng
发表于 2021-08-13 11:51:41
解题思路: 1. 构建并查集 2. 判断区域是否重叠 3. 合并, 人数相加,新冠传递,坐标叠加 4. 返回新冠集合中的人数 class Pos: def __init__(self, x, y): self.x = x self.y 展开全文
头像 Tag_Kausal
发表于 2020-02-16 09:58:23
题解1:AC举个例子,比如有4个线段,我们的是。。那么在叠加后如图:通过例子我们可以知道我们需要看红色线段与多少个线段是“联通”的,这就是我们要找的答案。那么如何找这个联通的个数呢?我们可以贪心的去找。按照左端点从小到大排序,维护右界的最大值,我们就可以知道每一坨连续的区间包含了多少个线段,再看的线 展开全文
头像 Ivy2019
发表于 2022-09-30 22:03:36
描述 牛牛刚刚得知牛牛所在的街道上有一个人得了新型冠状病毒!!!由于新型冠状病毒传染力很强,所以,只要在被传染的人的活动范围内活动都有可能被感染!现根据大数据可以得知,初始患病人在整个街道人群中的序号Pid和每个人在街道上的活动区域Pos。因为情况紧急,所以牛牛想请你帮忙快速计算下 展开全文
头像 AimerAimer
发表于 2021-10-12 19:28:44
题意:         给定多个区间和一个受感染的区间,问与受感染区间相交集的总个数。            &nb 展开全文
头像 牛客313925129号
发表于 2021-09-30 15:56:04
题意理解 每个人的活动范围相当于一个闭区间,开始时有一个人被感染。由于闭区间之间可能存在交集,所以当一个闭区间被感染时,与它相交的闭区间也会被感染,这个过程是瞬间完成的。所以,假设被感染的闭区间集合为S,还未被感染的闭区间集合为E,找出E中与S相交的闭区间,它们被感染并加入到S,更新E;不断迭代该过 展开全文
头像 摸鱼学大师
发表于 2021-08-06 21:13:29
思路: 题目的主要信息: 数组PeoplePosition是每个人活动的区间,Personid表示感染者的下标 所有感染者直接活动过的区间,或者与之直接相交的区间,或者与之间接交叉的区间(与前面两个的并集相交)都视作感染区间 活动范围与感染区间有交集的人视为感染者计数,求最后的感染人数 下标从0开 展开全文