hash方法的进阶

题目：https://ac.nowcoder.com/acm/contest/8564/A

import java.util.*;
public class Main {
    public static void main(String[] args) {
        Map<Integer, Integer> map = new HashMap<Integer, Integer>();
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        int AllVal = 0;
        int max = 0;
        int a[] = new int[n];
        int dis[] = new int[m];
        int val[] = new int[m];
        for (int i = 0; i < n; i++) {
            a[i] = sc.nextInt();
        }
        for (int i = 0; i < m; i++) {
            dis[i] = sc.nextInt();
        }
        for (int i = 0; i < m; i++) {
            val[i] = sc.nextInt();
            if(map.get(dis[i])!=null)
                map.put(dis[i], Math.max(map.get(dis[i]), val[i]));
            else
                map.put(dis[i], val[i]);
        }
        Arrays.sort(dis);
        Arrays.sort(a);
        int j;
        int k = 0;
        for (int i = 0; i<n ; i++) {
            for (  j = k; j < m; j++) {
                if(a[i]>dis[j]){
                    max = Math.max(max, map.get(dis[j]));
                }
                else {
                    break;
                }
            }
            k = j;
            AllVal += max;
        }
        System.out.println(AllVal);
    }
}

首先，自己的思路是利用枚举法，但是，借鉴了别人的代码之后发现了自己的许多问题，比如说，利用枚举法的时候，自己的方***忽略题目条件，就是一个战斗机只能攻击一次，所以我们要挑最大价值的基地攻击，但是自己的方***吧所有能攻击的基地的价值都加上，所以错得很离谱。借鉴别人的代码之后呢，就清晰明了了，大佬利用的是hashmap，先把价值与基地一起绑定，那么在绑定的时候避免不了有相同防御力的基地，但是别的价值更大，那就可以只改变基地的价值（这是hash表可以轻松）

 if(map.get(dis[i])!=null)
                map.put(dis[i], Math.max(map.get(dis[i]), val[i]));
            else
                map.put(dis[i], val[i]);

这里就是判断如果如果这一个基地不为空，他已经存在了价值，那么就选出两个价值中最高的一个，存入到这个基地中，也就是说只取这个基地价值最大化，就能保证我们得到的价值最大化。

for (int i = 0; i<n ; i++) {
            for (  j = k; j < m; j++) {
                if(a[i]>dis[j]){
                    max = Math.max(max, map.get(dis[j]));
                }
                else {
                    break;
                }
            }
            k = j;
            AllVal += max;
        }

最后再上面循环的时候，利用max模拟价值的最大化，因为我们已经排序好了两个数列。一直拿战斗机和基地防御力pk，一直用当前的最大价值max和这个基地的最大价值对比，将最大者继续赋值给max。当if条件不成立的时候也就是战斗机打不过的时候，我们就可以结束循环，得到最大max。
这里说一下（为什么不是int j = 0）,应该是减少算法复杂度吧，虽然我不知道算这个东西啊哈哈哈哈哈，