算法（三十八）

1、用户模型文件去重。

抖音上不同的用户类型我们有不同的用户模型文件。我们有一个模型配置文件，里面有很多的不同用户类型和他们对应的模型文件。我们需要找出每个模型文件对应的是哪些用户类型。

给定一行输入，格式为：

a b

a表示这个用户的用户类型，b表示这个用户对应的模型文件。请你输出每个模型文件对应的用户类型。

注意：每个模型文件可能对应多个用户类型，用户类型之间用空格作为切分。

注意2：如果有多个用户类型输出，用户类型之间的排序按照字母表排序。

eg:

输入：

1

abc 1.txt

输出如下：

1.txt abc

public class test020 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int lineNum = sc.nextInt();sc.nextLine();
        Map<String, Set<String>> map =  new TreeMap<>();
        for(int i=0; i<lineNum; i++){
            String[] line = sc.nextLine().trim().split(" ");
            if(map.containsKey(line [1])){
                map.get(line[1]).add(line[0]);
            }else {
                Set<String> set = new TreeSet<>();
                set.add(line[0]);
                map.put(line[1], set);
            }
        }

        for(Map.Entry<String, Set<String>> entry: map.entrySet()){
            Set<String> set = entry.getValue();
            List<String> strings = new ArrayList<>(set);
//            Collections.sort(strings);

            System.out.print(entry.getKey()+" ");
            for(String s: strings) System.out.print(s+" ");
            System.out.println();

        }
    }
}

2、 贪心算法，补给饮用水
假设你要从0点开始沙漠旅行到终点D，总共D个站点，每走一公里消耗一升的水量，初始携带的水量为W，但是在路途中是可以补给到一些水的，这些站点的位置在pos数组中给出，在sup数组的对应位置给出了在站点能获得的水量多少。即：在pos[i] 站点能获得的水量为sup[i]，现在要求最少需要加多少次水，如果在路途中会被渴死，直接返回-1

public class test021 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int D = sc.nextInt();
        int W = sc.nextInt();
        int[] pos = new int[3];
        int[] sup = new int[3];
        for(int i=0; i<3; i++){
            pos[i] = sc.nextInt();
        }
        for(int i=0; i<3; i++){
            sup[i] = sc.nextInt();
        }
        System.out.print(D+" ");
        System.out.print(W);
        System.out.println();
        for (int j=0; j<3; j++){
            System.out.print(pos[j]+" ");
        }
        System.out.println();
        for (int k=0; k<3; k++){
            System.out.print(sup[k]+" ");
        }
        System.out.println();
        int res = solve(D, W, pos, sup);
        System.out.println("次数最少为："+res+"次");
    }

    public static int solve(int D, int W, int[] pos, int[] sup){
        int res = 0;

        // 用来指示在特定的水站有没有取过水，一个水站只能取一次水
        boolean[] used = new boolean[pos.length];

        // 旅行者现在所在的位置
        int curPos = 0;

        while (curPos<D){
            // 每次直接跳到能够着的最大位置，携带的水也会被喝光
            curPos+=W;
            W = 0;
            // 如果已经到达终点，则直接返回加了多少次水
            if(curPos>=D) return res;

            // 标记一下能获得最多水的水站在pos中的下标
            int maxIndex = -1;

            for(int i=0;i<pos.length;i++){
                // 当前还没到指定的水站，则不能从这些水站取水，直接break
                if(pos[i]>curPos) break;
                // 如果还没从该水站取水，则会看在这里取水能否得到最大的水量
                if(!used[i] && sup[i]>W) {
                    W = sup[i]; maxIndex = i;
                    System.out.println("W="+W);
                    System.out.println("maxIndex="+maxIndex);
                }
            }

            // 没水了，而且也没有水站可以取水，可能在路途上被渴死
            if(maxIndex==-1) return -1;

            used[maxIndex] = true;
            res++;
        }
        return res;
    }
}