题解 | #代理服务器#

贪心:

选取走最大步数的代理服务器，依次循环，由于第一次切换代理服务器不算开销，最后结果减一即可。

import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        while (scanner.hasNext()) {
            HashMap<String, Boolean> hashMap = new HashMap<>();
            int n = scanner.nextInt();
            for (int i = 0; i < n; i++) {
                hashMap.put(scanner.next(), true);
            }

            int m = scanner.nextInt();
            String[] b = new String[m];
            for (int i = 0; i < m; i++) {
                b[i] = scanner.next();
            }

            int count = 0;
            int i = 0;
            while (i < b.length) {
                int maxStep = getMaxStep(b, i, hashMap);
                if (maxStep == 0) {
                    count = 0;
                    break;
                }
                i += maxStep;
                count++;
            }
            System.out.println(count-1);

        }
    }

    private static int getMaxStep(String[] b, int start, HashMap<String, Boolean> hashMap) {
        int i = start;
        for (; i < b.length; i++) {
            if (hashMap.containsKey(b[i])) {
                hashMap.put(b[i], false);
            }
            if (allFalse(hashMap)) {
                reset(hashMap);
                return i - start;
            }
        }
        return i - start;
    }

    private static void reset(HashMap<String, Boolean> hashMap) {
        for (Map.Entry<String, Boolean> entry : hashMap.entrySet()) {
            hashMap.put(entry.getKey(), true);
        }
    }

    private static boolean allFalse(HashMap<String, Boolean> hashMap) {
        for (Map.Entry<String, Boolean> entry : hashMap.entrySet()) {
            if (entry.getValue()) {
                return false;
            }
        }
        return true;
    }
}