贪心算法解决新冠问题
2021/5/16 14:25:44
本文主要是介绍贪心算法解决新冠问题,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
问题描述:如果一个组织里有一个人疑似新冠病人,那么该组织里所有人都将被隔离。假定编号为1的人疑似新冠病人,统计将被隔离的总人数(包括编号为1的人)。
输入格式:输入的第一行包含两个整数:n m,其中n为总人数,m为组织数。从第2行开始,接下来的m行表示每个组织的人数和该组织里每个人的编号,每一行的第1个数字k表示组织总人数,接下来的k个数字表示该组织里的每个人的编号。
输出格式:输出一个整数,表示需要隔离的人数。
样例输入:
100 4
2 2 3
5 10 13 11 12 14
2 1 2
2 99 3
样例输出:
4
算法设计:
按照贪心思路,在最开始时将感染初始成员确定后,在检查每个组织时,要使被感染成员尽可能被包括在某个集体(即最大化感染成员),作为下一次遍历的根据。
设置一个哈希表hashset存储已经被感染的人员编号;
另设置一个哈希表hashset1用来存储已经被感染的组织。
- 输入设置
- 为了确保能出现贪心的初始条件,我们设置一个检查点判断是否出现初始感染者G1,若有则该组织被感染,则进行已感染操作
(把二维数组中的一维数组所在的行标作为组织名存入已感染组织hashset1中,同时将该组织中的所有人员存入已感染者hashset中。) - 在找到感染者后,hashset中已经有了成员。为了优化后续查找,我们在对后续输入中进行检查,如果输入中出现感染者就对该组织进行已感染操作。
if(hashset.contains(a[i][j])||a[i][j]==1) { //如果正在输入的成员在hashset中或为1 hashset1.add(i); //将该组织加入hashset1, for(int k=0;k<j;k++) { //将该组织在感染者之前输入的成员加入hashset hashset.add(a[i][k]); } } if(hashset1.contains(i)) { //继续输入之后的成员 hashset.add(a[i][j]); } }
2.查找感染者:
-
在输入操作结束后,若某组织感染者,hashset与hashset1中已经有了相应的感染人员和感染组织。
-
在遍历时如果出现感染组织hashset1中的组织名就跳过该组织(因为在输入数据时已经将其中的组织中的成员加入了hashset中,即已经遍历);
-
遍历某组织时,如果组织中的某一个成员属于hashset中的成员,将这个组织进行已感染操作,没有则进入下个组织遍历。
-
设置一个count计数器,记录是否在此次的整体遍历中是否出现了新的感染者,count不为0时再次进行整体遍历,防止有漏网之鱼。
//推荐测试案例: 100 5 2 7 8 2 2 3 2 3 4 2 4 5 2 1 5
- 返回hashset中的元素长度即是感染人数。
实例代码:
package 贪心算法; import java.util.HashSet; import java.util.Scanner; public class Test { int q,w; int a[][]; //用数组存储的组织与人数 HashSet<Integer> hashset=new HashSet<>(); //感染人员编号存储 HashSet<Integer> hashset1=new HashSet<>(); //存储已经感染的组织 Test(int m,int n){ q=m; w=n; a=new int[w][]; Scanner in=new Scanner(System.in); for(int i=0;i<w;i++) { int x=in.nextInt(); a[i]=new int[x]; for(int j=0;j<x;j++) { //输入组织中人员编号 a[i][j]=in.nextInt(); if(hashset.contains(a[i][j])||a[i][j]==1) { //如果正在输入的成员在hashset中或为1 hashset1.add(i); //将该组织加入hashset1, for(int k=0;k<j;k++) { //将该组织在感染者之前输入的成员加入hashset hashset.add(a[i][k]); } } if(hashset1.contains(i)) { //继续输入之后的成员 hashset.add(a[i][j]); } } } } int Find() { if(hashset1.size()<=0) return 0; int count=0; //设置一个标记,如果该标记为零则代表在此次的遍历中已经没有新的感染者出现,如果有新感染者,则继续执行对下一次的Find()遍历 for(int i=0;i<w;i++) { if(!(hashset1.contains(i))) { //遍历未被感染的组织 for(int j=0;j<a[i].length;j++) { if(hashset.contains(a[i][j])) { //如果此编号在感染者中,该感染者所在组织已被感染 count++; //出现新的感染者 hashset1.add(i); //该感染者所在组织已被感染,将组织存入被感染组织hashset1中 for(int k=0;k<a[i].length;k++) { //存入组织中所有感染者 hashset.add(a[i][k]); } break; //跳出组织,进入下一个 } } } } if(count==0) return hashset.size(); //在此次的遍历中已经没有新的感染者出现,返回感染人数 else return Find(); //出现新患者,需要检查没被感染的组织中是否还有感染者 } } class Example{ public static void main(String[] args) { Scanner in=new Scanner(System.in); int m=in.nextInt(); //输入编号 int n=in.nextInt(); //输入组织号 Test test=new Test(m,n); System.out.println(test.Find()); } } //调试代码 //System.out.print("set "); //for(int key:hashset) //System.out.print(key+" "); //System.out.print('\n'+"set1 "); //for(int key:hashset1) // System.out.print(key+" "); //System.out.print('\n');
这篇关于贪心算法解决新冠问题的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-06-19《2023版Java工程师》课程升级公告
- 2024-06-15matplotlib作图不显示3D图,怎么办?
- 2024-06-1503-Loki 日志监控
- 2024-06-1504-让LLM理解知识 -Prompt
- 2024-06-05做软件测试需要懂代码吗?
- 2024-06-0514-ShardingSphere的分布式主键实现
- 2024-06-03为什么以及如何要进行架构设计权衡?
- 2024-05-31全网首发第二弹!软考2024年5月《软件设计师》真题+解析+答案!(11-20题)
- 2024-05-31全网首发!软考2024年5月《软件设计师》真题+解析+答案!(21-30题)
- 2024-05-30【Java】百万数据excel导出功能如何实现