阳江市网站建设_网站建设公司_H5网站_seo优化

(新卷,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))