import java.util.*;
/**
 * @author 必燃
 * @version 1.0
 * @create 2022-05-13 19:35 //开始日期
 */
public class 感染源在哪里 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        //人和地址集合
        HashMap<Person, HashSet<String>> map = new HashMap();
        //地址集合
        HashMap<String, Double> admap = new HashMap();
        //数据预处理
        for (int i = 0; i < n; i++) {
            if(i==0)
            {
                sc.nextLine();
            }
            String s = sc.nextLine();
            String[] ss = s.split(" ");
            admap.put(ss[1], 0.000);
            //System.out.println(admap.get(ss[1]));
            Person p = new Person(ss[0]);
            if (map.get(p) == null) {
                map.put(p, new HashSet());
            }
            //若加入else会导致第一个消失。
            map.get(p).add(ss[1]);
        }
        Set<Person> set = map.keySet();
        for (Person p :
                set) {
            p.cnt = map.get(p).size();
            for (String ad :
                    map.get(p)) {
                if (admap.containsKey(ad)) {
                        admap.put(ad, admap.get(ad) + (1.0 / p.cnt));
//                    System.out.println(1/p.cnt);
//                    System.out.println(admap.get(ad));
                }
            }
        }
        List<Map.Entry<String, Double>> list = new ArrayList<Map.Entry<String, Double>>(admap.entrySet());
        Collections.sort(list, new Comparator<Map.Entry<String, Double>>() {
            @Override
            public int compare(Map.Entry<String, Double> o1, Map.Entry<String, Double> o2) {
                int t =  (int)((o2.getValue())*1000 - (o1.getValue()*1000));
                if(t==0)
                {
                    return o1.getKey().compareTo(o2.getKey());
                }
                return t;
//                if (o2.getValue().equals(o1.getValue()) ) {
//                    return o1.getKey().compareTo(o2.getKey());
//                }
//                else if(o2.getValue() > o1.getValue())
//                {
//                    return 1;
//                }
//                else {
//                    return -1;
//                }
            }
        });
        for (Map.Entry<String, Double> e : list) {
            //System.out.println(e.getValue());
            System.out.println(e.getKey());
        }
    }
    public static class Person {
        String name;
        double cnt = 0.000;
        //double sum = 0;
        public Person(String s) {
            name = s;
        }
        @Override
        public boolean equals(Object o) {
            if (this == o) {
                return true;
            }
            if (o == null || getClass() != o.getClass()) {
                return false;
            }
            Person person = (Person) o;
            return Objects.equals(name, person.name);
        }
        @Override
        public int hashCode() {
            return Objects.hash(name);
        }
    }
}

关键点与问题

一人多次去一个地方，不计入分母次数，说明地点要与人进行一下绑定。
根据地点的得分为主关键字，地点字典顺序为次要关键字去排序。
人对应地点，地点对应得分，而地点的得分又依托于人物的轨迹，最后的排序又要依据地点的得分以及地点的字典顺序。
排序中会遇到问题，怎样将地点的得分与地点名字整合一起进行一个排序判断。并且在比较器重写过程中，因为得分极大可能是一个小数，小数之间的相减再强转int会导致精度丢失，误差很大。

代码思路
```
public static class Person {
     String name;
     double cnt = 0.000;
     //double sum = 0;

     public Person(String s) {
         name = s;
     }

     @Override
     public boolean equals(Object o) {
         if (this == o) {
             return true;
         }
         if (o == null || getClass() != o.getClass()) {
             return false;
         }
         Person person = (Person) o;
         return Objects.equals(name, person.name);
     }

     @Override
     public int hashCode() {
         return Objects.hash(name);
     }
 }
```
首先创建一个人物类，包含string的name属性和double的cnt属性。分别代表人的名字和所到过的地方总数。（cnt的改变用逻辑实现所去地点不重复。）其中建立构造器收录name，重写equals()与hashCode()使其Person类Name相同代表为相同对象。此处实现后续的人物存储时候避免重复存储同一人物。 :::info //人和地址集合
HashMap> map = new HashMap();
//地址集合
HashMap admap = new HashMap(); ::: 创建两个map，分别为map：人物（Person）-地点集合（HashSet）;admap：地址（String）-地址得分（Double）。
```
//数据预处理
     for (int i = 0; i < n; i++) {
         if(i==0)
         {
             sc.nextLine();
         }
         String s = sc.nextLine();
         String[] ss = s.split(" ");
         admap.put(ss[1], 0.000);
         //System.out.println(admap.get(ss[1]));
         Person p = new Person(ss[0]);
         if (map.get(p) == null) {
             map.put(p, new HashSet());
         }
         //若加入else会导致第一个消失。
         map.get(p).add(ss[1]);
     }
```
数据预处理：
每行输入都输入一行字符串，包含名字和地点。在输入n之后会有一个回车，用一个nextLine()吸收回车。
用split()进行分割字符串，在此行字符串中，ss[0]代表名字，ss[1]代表地址。此处将地址集合admap进行初始化。
此后利用ss[0]实例化Person对象P，若map中无法找到此时P对象所对应的Value，则用put将new匿名类HashSet添加到map中去（此时添加的HashSet为空）。后续再利用map.get(p).add(ss[1]);将此时的地址添加到此时map中P所对应的Value（即此人物对应的地址集合）中。
为方便解读，下文的人物P代表遍历状态下此时的Person对象，map的Value都代表此时人物P对应的地址集合。
数据预处理后达到一个状态：
1. map中存储人物-地址集合，所输入的所有人都会进行相应处理，将此人物去过的所有地点添加到此人物对应的地址集合（P所对应的HashSet中）中去。
2. admap中则存储了所有地址，但此时所有地址所对应得分都是0.0
```
Set<Person> set = map.keySet();
  for (Person p :
          set) {
      p.cnt = map.get(p).size();
      for (String ad :
              map.get(p)) {
          if (admap.containsKey(ad)) {
                  admap.put(ad, admap.get(ad) + (1.0 / p.cnt));
//                    System.out.println(1/p.cnt);
//                    System.out.println(admap.get(ad));
          }
      }
  }
```
  此后我们便可以通过遍历，逐个将map中的Value的size()赋值给P.cnt，再进行逐个运算，如果admap中的K（地址）包括此时P的地址ad，那么将此时的admap中ad所对应的值加上(1.0 / p.cnt)。
  拓展：上文的Map遍历方式有六种方式
  - 取出所有Key //常用方法
    1. 增强for循环
    2. 迭代器遍历
  上述两种方法直接使用map中的Keyset取出所有Key的集合，然后依次使用get方法获取Value进行遍历输出
  - 取出Value遍历 //Values方法取出所有Value到一个Collection中
    1. 增强for循环
    2. 迭代器
  上述两种直接使用Value变量输出就好
  - 通过EntrySet获取k-v来遍历输出
    1. 增强for循环
    2. 迭代器
  上述两种使用EntrySet取出Entry的集合，使用getKey()与getValue()方法遍历即可下文中的一个排序的实现就是取出Entry集合的方法。

如此遍历，最后进行一个排序，此排序有些复杂，但写的时候思路较为清晰。一班的TreeMap排序默认按照Key来排序，即使匿名内部类传入重写比较器也无法利用Value来进行比较。所以要么收录出所有的Key来进行一个算法的排序和存储，要么就把所有的Key或者Value取出放在一个集合中进行工具排序。

List<Map.Entry<String, Double>> list = new ArrayList<Map.Entry<String, Double>>(admap.entrySet());
        Collections.sort(list, new Comparator<Map.Entry<String, Double>>() {
            @Override
            public int compare(Map.Entry<String, Double> o1, Map.Entry<String, Double> o2) {
                int t =  (int)((o2.getValue())*1000 - (o1.getValue()*1000));

                if(t==0)
                {
                    return o1.getKey().compareTo(o2.getKey());
                }
                return t;
//                if (o2.getValue().equals(o1.getValue()) ) {
//                    return o1.getKey().compareTo(o2.getKey());
//                }
//                else if(o2.getValue() > o1.getValue())
//                {
//                    return 1;
//                }
//                else {
//                    return -1;
//                }

            }
        });

取出Map中封装的Entry对象，此对象就是将K-V变成了一个单列集合，因此可以直接给到ArrayList中。而后使用集合工具类的排序方法sort()进行排序，记得添加比较器。
比较器重写中的问题
注意如果遇到在比较器中重写，想利用相减来进行排序比较。这个比较器常常是返回int类型的，如果要比较的关键词是double类型，直接用来相减后强转为int会损失精度，导致误差。如果是1以内就会自动转为0，这就代表两者相同，但事实并非如此。
在此题中，要么使用比较运算符进行判断返回，要么就找到此小数的最大有效位数（大概），将两个值都乘上相应的10的次方进行一个扩大，这样之后的强转整型就能最大限度不会破坏精度。
下方的向上取整方法是不可行的，因为若是单纯相减，会出现负小数，向上取整和正数的向上取整是不同的。
除非利用判断语句，向上取整和向下取整都使用。四舍五入取整是不能用在这里的，当然你要是硬刚使用if语句，咱就是说，小刀划屁股了。

向上取整：Math.ceil(double a) 向下取整：Math.floor(double a) 四舍五入取整：Math.round(double a) 这里要注意Math.round(double a)和Math.rint(double a)，四舍五入取整要用Math.round(double a)，千万不要用Math.rint(double a)。普通强转（int）xx【double】会直接舍弃小数，损失精度。

Python课程设计

M1-人做对象，对数据预处理。

关键点与问题

代码思路