华为OD机试真题 Java 实现【统一限载货物数最小值】【2023Q1 200分】-LMLPHP

一、题目描述

火车站附近的货物中转站负责将到站货物运往仓库,小明在中转站负责调度 2K 辆中转车(K辆干货中转车,K 辆湿货中转车)货物由不同供货商从各地发来,各地的货物是依次进站,然后小明按照卸货顺序依次装货到中转车,一个供货商的货只能装到一辆车上不能拆装,但
是一辆车可以装多家供货商的货:中转车的限载货物量由小明统一指定,在完成货物中转的前提下,请问中转车的统一限载货物数最小值为多少。

二、输入描述

第一行 length 表示供货商数量 1 <= length <= 10;
第二行 goods 表示供货数数组 1 <= goods[i] <= 10;
第三行 types[i]表示对应货物类型,types[i]等于 0 或者 1,其中 0 代表干货,1 代表湿货;
第四行 k 表示单类中转车数量 1 <= k <= goods.length;

三、输出描述

运行结果输出一个整数,表示中转车统一限载货物数。

备注:中转车最多跑一趟仓库。

四、题目解析

货物由不同供货商从各地发来,各地的货物是依次进站,然后小明按照卸货顺序依次装货到中转车,一个供货商的货只能装到一辆车上,不能拆装,但是一辆车可以装多家供货商的货;这意味着,我们不难改变输入的顺序,要按照输入的顺序去装车。并且干货只能装到干货车,
湿货只能装到湿货车。

比如用例 1 中:
4
3 2 6 3
0 1 1 0
2

第 1 个货物是: 干货,因此装到干货车
第 2 个货物是:湿货,由于湿货不难装到干货车,因此第一辆车只装一个货物就必须走。第二个货物需要装到一辆湿货车上。
第 3 个货物是:湿货,前一步的湿货车还没走,此时我们有两种选择。将第 3 个货物继续装到前面的湿货车上,即和第 2 个货物装一起,但是会导致最低限载被提高。将第 3 个货物装到下一辆湿货车上。
第 4 个货物是:干货,因此只能重新要一辆干货车,继续装载说到这里,大家可能已经感觉出来,连续的 0(干货)可以用一辆车运,也可以分成多辆车运,而一旦连续 0(干货)被中断,即出现了 1(湿货),则前面的干货车必须走,这个湿货需要申请一辆湿货车来运根据上面逻辑,我们可以将连续干货 和 连续湿货 对应的区间段统计出来:

连续干货:[3]、[3]

连续湿货:[2,6]

  • 如果连续干货的区间段数 刚好等于 k,则刚好每段连续干货,都可以分配一辆干货车;
  • 如果连续干货的区间段数<k,则出了必要的给每段分配一辆干货车外,还有多余的干货车可以继续分配:此时,我们应该将多段连续干货,按照和大小降序,优先给 和最大 的连续干货段多分配一辆车,即相当于将一个区间一分为二,这样最低限载就降低了,并且多出的干货车数量减 1。如果多余的干货车数量不等于 0,则继续按上面逻辑,分配一辆车给 和最大 的连续干货段。直到多余的干货车用完。
  • 如果连续干货的区间段数 >k,此时是无法完成运输任务的,应该视为异常情况,但是本题没有说明异常处理,因此可以认为此场景不存在。

上面逻辑中,每次将区间一份为二后,都要重新按照 区间和大小降序,这里可以用 优先队列。

五、Java算法源码

public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt();
    int[] goods = new int[n];
    for (int i = 0; i < n; i++) {
        goods[i] = sc.nextInt();
    }
    int[] types = new int[n];
    for (int i = 0; i < n; i++) {
        types[i] = sc.nextInt();
    }
    int k = sc.nextInt();
    System.out.println(getResult(n, goods, types, k));
}

public static int getResult(int n, int[] goods, int[] types, int k) {
    PriorityQueue<LinkedList<Integer>> drys = new PriorityQueue<>((a, b) -> b.get(0) - a.get(0));
    PriorityQueue<LinkedList<Integer>> wets = new PriorityQueue<>((a, b) -> b.get(0) -
            a.get(0));
    boolean isDry = true;
    LinkedList<Integer> tmp = new LinkedList<>();
    int sum = 0;
    for (int i = 0; i < n; i++) {
        if (types[i] == 0) {
            if (isDry) {
                tmp.add(goods[i]);
                sum += goods[i];
            } else {
                tmp.addFirst(sum);
                wets.offer(tmp);
                tmp = new LinkedList<>();
                sum = 0;
                tmp.add(goods[i]);
                sum += goods[i];
                isDry = true;
            }
        } else {
            if (isDry) {
                tmp.addFirst(sum);
                drys.offer(tmp);
                tmp = new LinkedList<>();
                sum = 0;
                tmp.add(goods[i]);
                sum += goods[i];
                isDry = false;
            } else {
                tmp.add(goods[i]);
                sum += goods[i];
            }
        }
    }
    tmp.addFirst(sum);
    if (isDry) {
        drys.offer(tmp);
    } else {
        wets.offer(tmp);
    }
    int dry_min = divide(drys, k);
    int wet_min = divide(wets, k);
    return Math.max(dry_min, wet_min);
}

public static int divide(PriorityQueue<LinkedList<Integer>> goods, int k) {
    while (goods.size() < k) {
        LinkedList<Integer> top = goods.poll();
        if (top == null) break;
        int dry_sum = top.removeFirst();
        if (top.size() == 1) {
            return dry_sum;
        }
        int splitIdx = 0;
        int splitHalf = 0;
        int half = 0;
        int min = dry_sum;
        for (int i = 1; i < top.size(); i++) {
            int val = top.get(i - 1);
            half += val;
            int max = Math.max(half, dry_sum - half);
            if (max < min) {
                min = max;
                splitIdx = i;
                splitHalf = half;
            }
        }
        LinkedList<Integer> halfList = new LinkedList<>();
        halfList.add(splitHalf);
        halfList.addAll(top.subList(0, splitIdx));
        goods.offer(halfList);
        LinkedList<Integer> otherHalfList = new LinkedList<>();
        otherHalfList.add(dry_sum - splitHalf);
        otherHalfList.addAll(top.subList(splitIdx, top.size()));
        goods.offer(otherHalfList);
    }
    return goods.peek().get(0);
}

六、效果展示

1、输入

4
3 2 6 3
0 1 1 0
2

2、输出

6

华为OD机试真题 Java 实现【统一限载货物数最小值】【2023Q1 200分】-LMLPHP


🏆本文收录于,华为OD机试(JAVA)(2022&2023)

本专栏包含了最新最全的2023年华为OD机试真题,有详细的分析和Java解答。已帮助1000+同学顺利通过OD机考。专栏会持续更新,每天在线答疑。

华为OD机试真题 Java 实现【统一限载货物数最小值】【2023Q1 200分】-LMLPHP

05-17 03:58