Java-探险安排-HashMap+二分查找

• 对着原作者的C++版写的Java版
• 算法
  • 1.如果食物包裹数比总人数还少，一天都持续不了，返回0
  • 2.把食物类型及对应数目存放到map中
  • 3.持续天数最少为1，最多为m/n，做二分查找
    • 检查mid：map中的values除mid求和如果大于等于n说明可以持续mid天

import java.util.HashMap;
import java.util.Scanner;

public class AdventureArrange {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int m = scanner.nextInt();
        int[] foods = new int[m];
        for (int i = 0; i < m; i++) {
            foods[i] = scanner.nextInt();
        }
        System.out.println(adventureArrange(n, m, foods));
    }

    public static int adventureArrange(int n, int m, int[] foods) {
        if (m < n) {
            return 0;
        }

        HashMap<Integer, Integer> map = new HashMap<>();
        for (int x : foods) {
            int value = map.getOrDefault(x,0);
            map.put(x,value+1);
        }

        int l = 1;
        int r = m / n;
        while (l < r) {
            int mid = (l + r) >> 1;
            if (check(n, mid, map)) {
                l = mid + 1;
            } else {
                r = mid - 1;
            }
        }
        if (check(n, l, map)) {
            return l;
        } else {
            return l - 1;
        }
    }

    public static boolean check(int n, int x, HashMap<Integer, Integer> map) {
        int sum = 0;
        for (Integer integer : map.values()) {
            sum += integer / x;
        }
        return sum >= n;
    }
}