华为OD题目：统一限载货物数最小值

华为OD机试 - 统一限载货物数最小值

题目描述
火车站附近的货物中转站负责将到站货物运往仓库，小明在中转站负责调度2K辆中转车K辆干货中转车，K辆湿货中转车)。货物由不同供货商从各地发来，各地的货物是依次进站，然后小明按照卸货顺序依次装货到中转车，一个供货商的货只能装到一辆车上不能拆装，但是一辆车可以装多家供货商的货;
中转车的限载货物量由小明统一指定，在完成货物中转的前提下，请问中转车的统一限载货物数最小值为多少
输入描述
。第一行 length 表示供货商数量 1 <= length <= 10^4
第二行 goods 表示供货数数组 1 <= goods <= 10^4o
第三行 types表示对应货物类型，types[等于0或者1，:其中0代表干货，1代表湿货
第四行 k表示单类中转车数量 1 <= k <= goods.length
输出描述
运行结果输出一个整数，表示中转车统一限载货物数
备注
中转车最多跑一趟仓库

示例1
输入:
4
3 2 6 3
0 1 1 0
2

输出:
6

说明:
货物1和货物4为干货，由2两干货中转车中转，每辆车运输一个货物，限载为3
货物2和货物3为湿货，由2两湿货中转车中转，每辆车运输一个货物，限载为6
这样中转车统一限载货物数可以设置为6(千货车和湿货车限载最大值)，是最小的取值
示例2
输入:
4
3 2 6 8
0 1 1 1
1
输出:
16

说明:
货物1为千货，由1两工货中转车中转，限载为3
货物2、货物3和货物4为湿货，由1两湿货中转车中转，限载为16
这样中转车统一限载货物数可以设置为16 (千货车和湿货车限载最大值)，是最小的取值

public class My {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String lenStr = sc.nextLine();
        int len = Integer.parseInt(lenStr);


        String[] strings = sc.nextLine().split(" ");
        int[] goods = Arrays.stream(strings).mapToInt(Integer::parseInt).toArray();

        String[] typeStr = sc.nextLine().split(" ");
        int[] types = Arrays.stream(typeStr).mapToInt(Integer::parseInt).toArray();

        int k = Integer.parseInt(sc.nextLine());
        int result = getResult(len, goods, types, k);
        System.out.println(result);

    }

    public static int getResult(int len, int[] goods, int[] types, int k) {
        int left = 0;
        int right = 0;
        for (int i = 0; i < len; i++) {
            left = Math.max(left, goods[i]);
            right += goods[i];
        }

        while (left < right) {
            int mid = (left + right) / 2;
            if (canDivide(len, goods, types, k, mid)) {
                right = mid;
            }else {
                left = mid + 1;
            }
        }
        return left;

    }

    public static boolean canDivide(int len, int[] goods, int[] types, int k, int limit) {
        int dryCount = 0;
        int wetCount = 0;
        int drySum = 0;
        int wetSum = 0;

        for (int i = 0; i < len; i++) {
            //0-干货， 1-湿货
            if (types[i] == 0) {
                //看这一批 加上 当前货物是否在容量内
                if (drySum + goods[i] <= limit) {
                    drySum += goods[i];
                }else {
                    //如果超出容量了，则需要再加车
                    if (dryCount + 1 == k) {
                        // 没有可用的干货车了，则说明此limit无法完成所有货物的运输，直接返回false
                        return false;
                    }else {
                        // 有可用的干货车，则说明已用掉的干货车数量dryCarCount++，新的干货车装入当前货物goods[i]
                        dryCount++;
                        drySum = goods[i];
                    }
                }
            }else {
                if (wetSum + goods[i] <= limit) {
                    wetSum += goods[i];
                }else {
                    if (wetCount + 1 == k) {
                        return false;
                    }else {
                        wetCount++;
                        wetSum = goods[i];
                    }
                }
            }
        }
        return true;
    }

}