当前位置:   article > 正文

华为OD-D卷精准核酸检测

华为OD-D卷精准核酸检测

为了达到新冠疫情精准防控的需要,为了避免全员核酸检测带来的浪费,需要精准圈定可能被感染的人群。
现在根据传染病流调以及大数据分析,得到了每个人之间在时间、空间上是否存在轨迹的交叉。
现在给定一组确诊人员编号(X1, X2, X3, .... Xn),在所有人当中,找出哪些人需要进行核酸检测,输出需要进行核酸检测的人数。(注意:确诊病例自身不需要再做核酸检测)
需要进行核酸检测的人,是病毒传播链条上的所有人员,即有可能通过确诊病例所能传播到的所有人。
例如:A是确诊病例,A和B有接触、B和C有接触、C和D有接触、D和E有接触,那么B\C\D\E都是需要进行核酸检测的人。

输入描述:

第一行为总人数N

第二行为确诊病例人员编号(确诊病例人员数量<N),用逗号分割

第三行开始,为一个N*N的矩阵,表示每个人员之间是否有接触,0表示没有接触,1表示有接触。

输出描述:

整数:需要做核酸检测的人数

备注:

人员编号从0开始

0<N<100

题目解析:其实就是循环的去遍历确诊病例找到接触的人员,然后把接触人员也遍历下继续找就行,唯一需要注意的是,遍历的过程可能遇到重复的接触人员,最好通过set进行去重就好了,最后返回set的大小,记得返回的目标值要减去确诊人员数量。

  1. import java.util.*;
  2. public class Main {
  3. public static void main(String[] args) {
  4. // int n = 5;
  5. // int[] target = new int[]{1, 2};
  6. // int[][] nums = new int[][]{{1, 1, 0, 1, 0}, {1, 1, 0, 0, 0}, {0, 0, 1, 0, 1}, {1, 0, 0, 1, 0}, {0, 0, 1, 0, 1}};
  7. // 处理数据
  8. Scanner scanner = new Scanner(System.in);
  9. int n = scanner.nextInt();
  10. String[] string1 = scanner.next().split(",");
  11. int[] target = new int[string1.length];
  12. for (int i = 0; i < target.length; i++) {
  13. target[i] = Integer.parseInt(string1[i]);
  14. }
  15. int[][] nums = new int[n][n];
  16. for (int i = 0; i < n; i++) {
  17. String[] string = scanner.next().split(",");
  18. for (int j = 0; j < n; j++) {
  19. nums[i][j] = Integer.parseInt(string[j]);
  20. }
  21. }
  22. // stack用于存储确诊人员和接触人员,依次从里面找
  23. Stack<Integer> stack = new Stack();
  24. // set进行去重,避免死循环
  25. HashSet<Integer> set = new HashSet<>();
  26. for (int i = 0; i < target.length; i++) {
  27. set.add(target[i]);
  28. stack.push(target[i]);
  29. }
  30. while (!stack.isEmpty()) {
  31. Integer pop = stack.pop();
  32. // 两个for循环判断是否存在秘接人员,注意set去重
  33. for (int i = 0; i < n; i++) {
  34. if (nums[i][pop] != 1 || set.contains(i)) {
  35. continue;
  36. }
  37. stack.add(i);
  38. set.add(i);
  39. }
  40. for (int i = 0; i < n; i++) {
  41. if (nums[pop][i] != 1 || set.contains(i)) {
  42. continue;
  43. }
  44. stack.add(i);
  45. set.add(i);
  46. }
  47. }
  48. System.out.println(set.size() - target.length);
  49. }
  50. }

声明:本文内容由网友自发贡献,转载请注明出处:【wpsshop】
推荐阅读
相关标签
  

闽ICP备14008679号