企业官网建设流程全解析

钟祥网站制作,河北建设协会官方网站,湖州网站建设公司哪家好,注册公司需要几个人员(新卷,100分)- 统一限载货物数最小值#xff08;Java JS Python#xff09;题目描述火车站附近的货物中转站负责将到站货物运往仓库#xff0c;小明在中转站负责调度2K辆中转车#xff08;K辆干货中转车#xff0c;K辆湿货中转车#xff09;。货物由不同供货…(新卷,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输出描述运行结果输出一个整数表示中转车统一限载货物数备注中转车最多跑一趟仓库用例输入43 2 6 30 1 1 02输出6说明货物1和货物4为干货由2辆干货中转车中转每辆车运输一个货物限载为3货物2和货物3为湿货由2辆湿货中转车中转每辆车运输一个货物限载为6这样中转车统一限载货物数可以设置为6干货车和湿货车限载最大值是最小的取值输入43 2 6 80 1 1 11输出16说明货物1为干货由1辆干货中转车中转限载为3货物2、货物3、货物4为湿货由1辆湿货中转车中转限载为16这样中转车统一限载货物数可以设置为16干货车和湿货车限载最大值是最小的取值题目解析本题经过和考友沟通还是需要考虑装货顺序但是不同于前面考虑了顺序的解法之前考虑装货顺序的逻辑是每次只有一辆车在装货如果按顺序装货时当前货车遇到不同类型的货物则当前货车必须走和考友沟通后发现满分解法是这样设计装货逻辑的每次都有干湿两辆货车同时等待并且我们还是要按顺序装货且干货装入干货车湿货装入湿货车我们可以决定货车什么时候走一旦货车走了则下一辆同类型的货车继续补上只要还有对应类型的货车还有剩余。因此本题的难度大大降低了。我们完全可以将所有货物中最重的货物作为所有货车的最低限载。然后尝试该限载是否可以完成装货如果不可以则在此最低限载基础上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) { ArrayListInteger dry new ArrayList(); ArrayListInteger 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(ArrayListInteger 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, ArrayListInteger 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(reverseTrue) 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))