(A卷,100分)- 统一限载货物数最小值（Java & JS & Python）

题目描述

火车站附近的货物中转站负责将到站货物运往仓库，小明在中转站负责调度2K辆中转车（K辆干货中转车，K辆湿货中转车）。

货物由不同供货商从各地发来，各地的货物是依次进站，然后小明按照卸货顺序依次装货到中转车，一个供货商的货只能装到一辆车上，不能拆装，但是一辆车可以装多家供货商的货；

中转车的限载货物量由小明统一指定，在完成货物中转的前提下，请问中转车的统一限载货物数最小值为多少。

输入描述

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

输出描述

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

备注

中转车最多跑一趟仓库

用例

题目解析

本题经过和考友沟通，还是需要考虑装货顺序，但是不同于前面考虑了顺序的解法

之前考虑装货顺序的逻辑是：

每次只有一辆车在装货，如果按顺序装货时，当前货车遇到不同类型的货物，则当前货车必须走

和考友沟通后，发现满分解法是这样设计装货逻辑的

每次都有干湿两辆货车同时等待，并且我们还是要按顺序装货，且干货装入干货车，湿货装入湿货车，我们可以决定货车什么时候走，一旦货车走了，则下一辆同类型的货车继续补上，只要还有对应类型的货车还有剩余。

因此本题的难度大大降低了。

我们完全可以将所有货物中，最重的货物作为所有货车的最低限载。然后尝试该限载，是否可以完成装货，如果不可以则在此最低限载基础上+1，然后继续尝试，如果可以，则直接返回。

更优的做法是使用二分法，即minLimit = max(goods)，maxLimit = sum(goods)，然后取中间值limit作为可能的最低限载去尝试装货。

如果能完成运输，则此时limit就是一个可能的解，但是不一定是最优解，我们需要继续尝试更小的limit。

如果不能完成运输，则此时limit必然取小了，我们需要尝试更大的limit。

考虑装货顺序（可得100%通过率）

Java算法源码

import java.util.Scanner;

public class Main {
  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));
  }

  /**
   * @param n 供货商数量
   * @param goods 供货数数组
   * @param types 表示对应货物类型，types[i]等于0或者1，其中0代表干货，1代表湿货
   * @param k 表示单类中转车数量
   * @return 中转车的统一限载货物数最小值为多少
   */
  public static int getResult(int n, int[] goods, int[] types, int k) {
    // 最低限载最小取值
    int minLimit = 0;
    // 最低限载最大取值
    int maxLimit = 0;
    for (int i = 0; i < n; i++) {
      // 所有货物中重量最大的作为minLimit，即每辆车至多放一个货物时，则此时最低限载为重量最大的货物
      minLimit = Math.max(minLimit, goods[i]);
      // 所有货物都放到一辆车上，则此时该车的载重就是maxLimit
      maxLimit += goods[i];
    }

    // 二分法尝试可能的最低限载limit
    while (minLimit <= maxLimit) {
      int limit = (minLimit + maxLimit) / 2;

      // 如果当前limit可以完成所有货物的运输，则当前limit为一个可能解，但不一定时最优解，我们可以尝试更小的最低限载
      if (canLimit(limit, n, goods, types, k)) {
        maxLimit = limit - 1;
      } else {
        // 如果当前limit不能完成所有货物的运输，则当前limit小了，我们应该尝试更大的limit
        minLimit = limit + 1;
      }
    }

    return minLimit;

    //    int limit = Arrays.stream(goods).max().orElse(0);
    //
    //    while (true) {
    //      if (canLimit(limit, n, goods, types, k)) {
    //        return limit;
    //      } else {
    //        limit++;
    //      }
    //    }
  }

  // 判断当前的limit最低限载是否可以完成所有货物的运输
  public static boolean canLimit(int limit, int n, int[] goods, int[] types, int k) {
    // dryCarCount是已用掉的干货车数量
    // wetCarCount是已用掉的湿货车数量
    int dryCarCount = 0, wetCarCount = 0;

    // dryCarSum是当前正在装货的干货车的载重
    // wetCarSum是当前正在装货的湿货车的载重
    int dryCarSum = 0, wetCarSum = 0;

    // 遍历每一个货物
    for (int i = 0; i < n; i++) {
      // 如果是干货
      if (types[i] == 0) {
        // 尝试将当前干货goods[i]放到当前的干货车上，看看放上去后，当前干货车的载重是否超过了limit
        if (dryCarSum + goods[i] <= limit) {
          // 没有超过limit，则装入
          dryCarSum += goods[i];
        } else {
          // 超过了limit，则继续看是否还有剩余可用的干货车
          if (dryCarCount + 1 == k) {
            // 没有可用的干货车了，则说明此limit无法完成所有货物的运输，直接返回false
            return false;
          } else {
            // 有可用的干货车，则说明已用掉的干货车数量dryCarCount++，新的干货车装入当前货物goods[i]
            dryCarCount += 1;
            dryCarSum = goods[i];
          }
        }
      } else {
        // 湿货逻辑同上
        if (wetCarSum + goods[i] <= limit) {
          wetCarSum += goods[i];
        } else {
          if (wetCarCount + 1 == k) {
            return false;
          } else {
            wetCarCount += 1;
            wetCarSum = goods[i];
          }
        }
      }
    }

    return true;
  }
}

JavaScript算法源码

/* JavaScript Node ACM模式 控制台输入获取 */
const readline = require("readline");

const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout,
});

const lines = [];
rl.on("line", (line) => {
  lines.push(line);

  if (lines.length === 4) {
    const n = lines[0] - 0;
    const goods = lines[1].split(" ").map(Number);
    const types = lines[2].split(" ").map(Number);
    const k = lines[3] - 0;

    console.log(getResult(n, goods, types, k));
    lines.length = 0;
  }
});

/**
 * @param {*} n 供货商数量
 * @param {*} goods 供货数数组
 * @param {*} types 表示对应货物类型，types[i]等于0或者1，其中0代表干货，1代表湿货
 * @param {*} k 表示单类中转车数量
 * @returns 中转车的统一限载货物数最小值为多少
 */
function getResult(n, goods, types, k) {
  // 最低限载最小取值
  let minLimit = 0;
  // 最低限载最大取值
  let maxLimit = 0;
  for (let good of goods) {
    // 所有货物中重量最大的作为minLimit，即每辆车至多放一个货物时，则此时最低限载为重量最大的货物
    minLimit = Math.max(minLimit, good);
    // 所有货物都放到一辆车上，则此时该车的载重就是maxLimit
    maxLimit += good;
  }

  // 二分法尝试可能的最低限载limit
  while (minLimit <= maxLimit) {
    const limit = Math.floor((minLimit + maxLimit) / 2);

    // 如果当前limit可以完成所有货物的运输，则当前limit为一个可能解，但不一定时最优解，我们可以尝试更小的最低限载
    if (canLimit(limit, n, goods, types, k)) {
      maxLimit = limit - 1;
    } else {
      // 如果当前limit不能完成所有货物的运输，则当前limit小了，我们应该尝试更大的limit
      minLimit = limit + 1;
    }
  }
  return minLimit;

  // 暴力法
  //   let limit = Math.max(...goods);
  //   while (true) {
  //     if (canLimit(limit, n, goods, types, k)) {
  //       return limit;
  //     } else {
  //       limit++;
  //     }
  //   }
}

// 判断当前的limit最低限载是否可以完成所有货物的运输
function canLimit(limit, n, goods, types, k) {
  // dryCarCount是已用掉的干货车数量
  // dryCarSum是当前正在装货的干货车的载重
  let dryCarCount = 0,
    dryCarSum = 0;

  // wetCarCount是已用掉的湿货车数量
  // wetCarSum是当前正在装货的湿货车的载重
  let wetCarCount = 0,
    wetCarSum = 0;

  // 遍历每一个货物
  for (let i = 0; i < n; i++) {
    // 如果是干货
    if (types[i] == 0) {
      // 尝试将当前干货goods[i]放到当前的干货车上，看看放上去后，当前干货车的载重是否超过了limit
      if (dryCarSum + goods[i] <= limit) {
        // 没有超过limit，则装入
        dryCarSum += goods[i];
      } else {
        // 超过了limit，则继续看是否还有剩余可用的干货车
        if (dryCarCount + 1 == k) {
          // 没有可用的干货车了，则说明此limit无法完成所有货物的运输，直接返回false
          return false;
        } else {
          // 有可用的干货车，则说明已用掉的干货车数量dryCarCount++，新的干货车装入当前货物goods[i]
          dryCarCount += 1;
          dryCarSum = goods[i];
        }
      }
    } else {
      // 湿货逻辑同上
      if (wetCarSum + goods[i] <= limit) {
        wetCarSum += goods[i];
      } else {
        if (wetCarCount + 1 == k) {
          return false;
        } else {
          wetCarCount += 1;
          wetCarSum = goods[i];
        }
      }
    }
  }

  return true;
}

Python算法源码

# 输入获取
n = int(input())
goods = list(map(int, input().split()))
types = list(map(int, input().split()))
k = int(input())


# 判断当前的limit最低限载是否可以完成所有货物的运输
def canLimit(limit, n, goods, types, k):
    # dryCarCount是已用掉的干货车数量
    dryCarCount = 0
    # dryCarSum是当前正在装货的干货车的载重
    dryCarSum = 0

    # wetCarCount是已用掉的湿货车数量
    wetCarCount = 0
    # wetCarSum是当前正在装货的湿货车的载重
    wetCarSum = 0

    # 遍历每一个货物
    for i in range(n):
        # 如果是干货
        if types[i] == 0:
            # 尝试将当前干货goods[i]放到当前的干货车上，看看放上去后，当前干货车的载重是否超过了limit
            if dryCarSum + goods[i] <= limit:
                # 没有超过limit，则装入
                dryCarSum += goods[i]
            else:
                # 超过了limit，则继续看是否还有剩余可用的干货车
                if dryCarCount + 1 == k:
                    # 没有可用的干货车了，则说明此limit无法完成所有货物的运输，直接返回false
                    return False
                else:
                    # 有可用的干货车，则说明已用掉的干货车数量dryCarCount++，新的干货车装入当前货物goods[i]
                    dryCarCount += 1
                    dryCarSum = goods[i]
        else:
            # 湿货逻辑同上
            if wetCarSum + goods[i] <= limit:
                wetCarSum += goods[i]
            else:
                if wetCarCount + 1 == k:
                    return False
                else:
                    wetCarCount += 1
                    wetCarSum = goods[i]

    return True


# 算法入口
def getResult(n, goods, types, k):
    """
    :param n: 供货商数量
    :param goods: 供货数数组
    :param types: 表示对应货物类型，types[i]等于0或者1，其中0代表干货，1代表湿货
    :param k: 表示单类中转车数量
    :return: 中转车的统一限载货物数最小值为多少
    """
    # 暴力法
    # limit = max(goods)
    # while True:
    #     if canLimit(limit, n, goods, types, k):
    #         return limit
    #     else:
    #         limit += 1

    # 最低限载最小取值,所有货物中重量最大的作为minLimit，即每辆车至多放一个货物时，则此时最低限载为重量最大的货物
    minLimit = max(goods)
    # 最低限载最大取值,所有货物都放到一辆车上，则此时该车的载重就是maxLimit
    maxLimit = sum(goods)

    # 二分法尝试可能的最低限载limit
    while minLimit <= maxLimit:
        limit = (minLimit + maxLimit) // 2

        # 如果当前limit可以完成所有货物的运输，则当前limit为一个可能解，但不一定时最优解，我们可以尝试更小的最低限载
        if canLimit(limit, n, goods, types, k):
            maxLimit = limit - 1
        else:
            # 如果当前limit不能完成所有货物的运输，则当前limit小了，我们应该尝试更大的limit
            minLimit = limit + 1

    return minLimit


# 算法调用
print(getResult(n, goods, types, k))

不考虑装货顺序（可得25%通过率）

如果本题不考虑装货顺序，其实就是

的变种题。

解析大家可以看上面链接博客。

JavaScript算法源码

/* JavaScript Node ACM模式 控制台输入获取 */
const readline = require("readline");

const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout,
});

const lines = [];
rl.on("line", (line) => {
  lines.push(line);

  if (lines.length === 4) {
    const n = lines[0] - 0;
    const goods = lines[1].split(" ").map(Number);
    const types = lines[2].split(" ").map(Number);
    const k = lines[3] - 0;

    console.log(getResult(n, goods, types, k));
    lines.length = 0;
  }
});

/**
 * @param {*} n 供货商数量
 * @param {*} goods 供货数数组
 * @param {*} types 表示对应货物类型，types[i]等于0或者1，其中0代表干货，1代表湿货
 * @param {*} k 表示单类中转车数量
 * @returns 中转车的统一限载货物数最小值为多少
 */
function getResult(n, goods, types, k) {
  const dry = [];
  const wet = [];

  for (let i = 0; i < n; i++) {
    if (types[i] == 0) {
      dry.push(goods[i]);
    } else {
      wet.push(goods[i]);
    }
  }

  return Math.max(getMinMaxWeight(dry, k), getMinMaxWeight(wet, k));
}

function getMinMaxWeight(weights, k) {
  const n = weights.length;

  if (n <= k) {
    return Math.max(...weights);
  }

  weights.sort((a, b) => b - a);

  let min = weights[0];
  let max = weights.reduce((p, c) => p + c);

  while (min < max) {
    const mid = (min + max) >> 1;

    const buckets = new Array(k).fill(0);
    if (check(0, weights, buckets, mid)) {
      max = mid;
    } else {
      min = mid + 1;
    }
  }

  return min;
}

function check(index, weights, buckets, limit) {
  if (index == weights.length) {
    return true;
  }

  const select = weights[index];
  for (let i = 0; i < buckets.length; i++) {
    if (buckets[i] + select <= limit) {
      buckets[i] += select;
      if (check(index + 1, weights, buckets, limit)) return true;
      buckets[i] -= select;
      if (buckets[i] == 0) return false;
    }
  }

  return false;
}

Java算法源码

import java.util.ArrayList;
import java.util.Scanner;

public class Main {
  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));
  }

  /**
   * @param n 供货商数量
   * @param goods 供货数数组
   * @param types 表示对应货物类型，types[i]等于0或者1，其中0代表干货，1代表湿货
   * @param k 表示单类中转车数量
   * @return 中转车的统一限载货物数最小值为多少
   */
  public static int getResult(int n, int[] goods, int[] types, int k) {
    ArrayList<Integer> dry = new ArrayList<>();
    ArrayList<Integer> wet = new ArrayList<>();

    for (int i = 0; i < n; i++) {
      if (types[i] == 0) {
        dry.add(goods[i]);
      } else {
        wet.add(goods[i]);
      }
    }

    return Math.max(getMinMaxWeight(dry, k), getMinMaxWeight(wet, k));
  }

  public static int getMinMaxWeight(ArrayList<Integer> weights, int k) {
    int n = weights.size();

    if (n <= k) {
      return weights.stream().max((a, b) -> a - b).orElse(0);
    }

    weights.sort((a, b) -> b - a);

    int min = weights.get(0);
    int max = weights.stream().reduce(Integer::sum).get();

    while (min < max) {
      int mid = (min + max) >> 1;

      int[] buckets = new int[k];
      if (check(0, weights, buckets, mid)) {
        max = mid;
      } else {
        min = mid + 1;
      }
    }

    return min;
  }

  public static boolean check(int index, ArrayList<Integer> weights, int[] buckets, int limit) {
    if (index == weights.size()) {
      return true;
    }

    int select = weights.get(index);
    for (int i = 0; i < buckets.length; i++) {
      if (buckets[i] + select <= limit) {
        buckets[i] += select;
        if (check(index + 1, weights, buckets, limit)) return true;
        buckets[i] -= select;
        if (buckets[i] == 0) return false;
      }
    }

    return false;
  }
}

Python算法源码

import queue

# 输入获取
n = int(input())
goods = list(map(int, input().split()))
types = list(map(int, input().split()))
k = int(input())


# 本方法用于验证当前limit是否符合要求
def check(index, weights, buckets, limit):
    if index == len(weights):
        return True

    select = weights[index]
    for i in range(len(buckets)):
        if buckets[i] + select <= limit:
            buckets[i] += select
            if check(index + 1, weights, buckets, limit):
                return True
            buckets[i] -= select
            if buckets[0] == 0:
                return False
    return False


# 本方法用于求解干货或湿货的最小限载
def getMaxMinWeight(weights, k):
    n = len(weights)

    if n <= k:
        return max(weights)

    weights.sort(reverse=True)

    low = weights[0]
    high = sum(weights)

    while low < high:
        mid = (low + high) // 2
        buckets = [0] * k

        if check(0, weights, buckets, mid):
            high = mid
        else:
            low = mid + 1

    return low


# 算法入口
def getResult(n, goods, types, k):
    dry = []
    wet = []

    for i in range(n):
        if types[i] == 0:
            dry.append(goods[i])
        else:
            wet.append(goods[i])

    return max(getMaxMinWeight(dry, k), getMaxMinWeight(wet, k))


# 算法调用
print(getResult(n, goods, types, k))