全网最全面的华为OD机试真题汇总，100%原题题库，不需要开会员即可查看全部内容，更多考题请查看真题库。
真题库：https://www.yuque.com/codernav.com/od
题目：统一限载货物数最小值
知识点二分查找
时间限制：1s 空间限制：64MB 限定语言：不限
题目描述：
火车站附近的货物中转站负责将到站货物运往仓库，小明在中转站负责调度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.中转车最多跑一趟仓库
示例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（干货车和湿货车限载最大值），是最小的取值
解题思路：
4
3 2 3 5
1 1 1 1
2
首先统计出湿货物的总重量countWet=3+2+3+5=13，湿货物列表listWet={3,2,3,5}；k为2，我们新建长度为2的数组vans=【0,0】作为货车载重数组；对货物列表进行排序{2,3,3,5}，方便后面的遍历。
求运送湿货物的最小货车载量：
1、题目中的k为2，也就是是说2辆车需要运送重量13的货物，由此我们可以求得13/2=6+1=7，每辆车的最小载量应该为7；湿货物中最大的货物重量为5；5<7，这样一来，我们的最小载量应该为7；而最大载量肯定就是货物的总量13
2、这里我们使用二分法：
1）7+13 / 2 = 10，假定载量为10；遍历货物列表：
Weight=2，遍历货车数组【0，0】；因为vans[0]+2<10，放在第一辆车【2,0】；
Weight=3，遍历货车数组【2,0】；因为vans[0]+3<10，放在第一辆车【5,0】；
Weight=3，遍历货车数组【5,0】；因为vans[0]+3<10，放在第一辆车【8,0】；
Weight=5，遍历货车数组【8,0】；因为vans[0]+5>10，vans[1]+5<10，放在第二辆车【8,5】
2）说明载重10是可以运输的，此时最小载重为7，最大载重10；那我们继续进行二分；7+10/2 = 8，假定载重为8；遍历货物列表：
Weight=2，遍历货车数组【0，0】；因为vans[0]+2<8，放在第一辆车【2,0】；
Weight=3，遍历货车数组【2,0】；因为vans[0]+3<8，放在第一辆车【5,0】；
Weight=3，遍历货车数组【5,0】；因为vans[0]+3<=8，放在第一辆车【8,0】；
Weight=5，遍历货车数组【8,0】；因为vans[0]+5>10，vans[1]+5<10，放在第二辆车【8,5】
3）说明载重8也是可以的，此时最小载重为7，最大载重8；继续二分：7+8/2=7，假定载重为7；遍历货物列表：
Weight=2，遍历货车数组【0，0】；因为vans[0]+2<7，放在第一辆车【2,0】；
Weight=3，遍历货车数组【2,0】；因为vans[0]+3<7，放在第一辆车【5,0】；
Weight=3，遍历货车数组【5,0】；因为vans[0]+3>7，vans[1]+5<7，放在第一辆车【5，3】；
Weight=5，遍历货车数组【8,0】；因为vans[0]+5>10，vans[1]+5>7，说明无法满足条件，进行回退；回退到第一次遍历的第一个循环【2，0】：开启第二次遍历的第一个循环，Weight=3，我们尝试将其放入第二辆车【2,3】；
Weight=3，遍历货车数组【2,3】；因为vans[0]+3<7，放在第一辆车【5,3】；
Weight=5，遍历货车数组【5,3】；因为vans[0]+5>7，vans[1]+5>7，说明无法满足条件，进行回退；回退到第二次遍历的第一个循环【2，3】：开启第三次遍历的第一个循环，Weight=3，我们尝试将其放入第二辆车【2,6】；
Weight=5，遍历货车数组【2,6】；因为vans[0]+5<=7，放在第一辆车【7,6】
3、最终结果为7
以上就是大体的解题思路，可能比较难懂，大家可以debug一下代码多尝试理解一下！这道题本身是比较难的，正确率也低，目前没有看到满分的！
代码实现一：
package com.codernav.demo.hwod.exam;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Scanner;
/**
* @title 统一限载货物数最小值
* @Description 火车站附近的货物中转站负责将到站货物运往仓库，小明在中转站负责调度2K辆中转车(K辆干货中转车，K辆湿货中转车)。
* 货物由不同供货商从各地发来，各地的货物是依次进站，然后小明按照卸货顺序依次装货到中转车上，
* 一个供货商的货只能装到一辆车上，不能拆装，但是一辆车可以装多家供货商的货；
* 中转车的限载货物量由小明统一制定，在完成货物中转的前提下，请问中转车的统一限载货物数最小值为多少。
* @Author 开发者导航
* @website https://codernav.com
* @date 2023/5/28
*/
public class Main {
public static int k;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int len = sc.nextInt();
int[] goods = new int[len];
for (int i = 0; i < len; i++) {
goods[i] = sc.nextInt();
}
int[] types = new int[len];
for (int i = 0; i < len; i++) {
types[i] = sc.nextInt();
}
k = sc.nextInt();
List<Integer> listDry = new ArrayList<>(); //干货物
List<Integer> listWet = new ArrayList<>(); //湿货物
int countDry = 0; //干货物总重
int countWet = 0; //湿货物总重
for (int i = 0; i < len; i++) {
int type = types[i];
int good = goods[i];
if (type == 0) {
listDry.add(good);
countDry += good;
} else {
listWet.add(good);
countWet += good;
}
}
Collections.sort(listDry);
Collections.sort(listWet);
int minDry = 0;
int minWet = 0;
if (listDry.size() != 0) {
minDry = handle(listDry, countDry);
}
if (listWet.size() != 0) {
minWet = handle(listWet, countWet);
}
int res = Math.max(minDry, minWet);
System.out.println(res);
}
/**
* 求出最小货物限载量
*
* @param goodList 货物集合
* @param count 货物总重
* @return
*/
public static int handle(List<Integer> goodList, int count) {
//最重货物
int maxList = goodList.get(goodList.size() - 1);
//平均每辆车放置的最低重量
int minWeight = count % k == 0 ? count / k : count / k + 1;
//最少限载货物量
int min = Math.max(maxList, minWeight);
//最大限载货物量（一辆车的时候）
int max = count;
//二分法
while (min < max) {
int mid = (min + max) / 2;
//K辆车（每次都需要初始化）
int[] vans = new int[k];
if (check(goodList, 0, vans, mid)) {
max = mid;
} else {
min = mid + 1;
}
}
return min;
}
/**
* 判断当前限载货物量是否能装完货物
*
* @param goods 货物集合
* @param index 货物索引
* @param vans 货车数组
* @param weight 限载货物量
* @return
*/
public static boolean check(List<Integer> goods, int index, int[] vans, int weight) {
// index == nums.length说明都放完了
if (index == goods.size()) {
return true;
}
for (int i = 0; i < vans.length; i++) {
//多辆车货物重量一样,前面已经试了不要重复试,此处可能不好理解
if (i > 0 && vans[i] == vans[i - 1]) {
continue;
}
// 满足条件才能放入
if (vans[i] + goods.get(index) <= weight) {
// 放入
vans[i] = vans[i] + goods.get(index);
// 后续递归放入剩余的货物
if (check(goods, index + 1, vans, weight)) {
return true;
}
//上面的策略失败了,就回退,继续尝试后面的策略
vans[i] = vans[i] - goods.get(index);
}
}
return false;
}
}
代码实现二：Java代码满分实现
package com.codernav.demo.hwod.exam;
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
/**
* @title 统一限载货物数最小值
* @Description 火车站附近的货物中转站负责将到站货物运往仓库，小明在中转站负责调度2K辆中转车(K辆干货中转车，K辆湿货中转车)。
* 货物由不同供货商从各地发来，各地的货物是依次进站，然后小明按照卸货顺序依次装货到中转车上，
* 一个供货商的货只能装到一辆车上，不能拆装，但是一辆车可以装多家供货商的货；
* 中转车的限载货物量由小明统一制定，在完成货物中转的前提下，请问中转车的统一限载货物数最小值为多少。
* @Author 开发者导航
* @website https://codernav.com
* @date 2023/5/28
*/
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int length = sc.nextInt();
int[] goods = new int[length];
int[] types = new int[length];
for (int i = 0; i < length; i++) {
goods[i] = sc.nextInt();
}
for (int i = 0; i < length; i++) {
types[i] = sc.nextInt();
}
int k = sc.nextInt();
int minGan = 0;
int maxGan = 0;
int minShi = 0;
int maxShi = 0;
List<Integer> ganGoods = new ArrayList<>();
List<Integer> shiGoods = new ArrayList<>();
for (int i = 0; i < length; i++) {
if (types[i] == 0) {
minGan = Math.max(goods[i], minGan);
maxGan += goods[i];
ganGoods.add(goods[i]);
} else {
minShi = Math.max(minShi, goods[i]);
maxShi += goods[i];
shiGoods.add(goods[i]);
}
}
if (k == 1) {
System.out.println(Math.max(maxGan, maxShi));
} else if (k >= Math.max(ganGoods.size(), shiGoods.size())) {
System.out.println(Math.max(minGan, minShi));
} else {
int minL = Math.max(minShi, minGan);
int maxL = Math.max(maxGan, maxShi);
while (minL <= maxL) {
int li = (maxL + minL) / 2;
if (candiv(li, length, ganGoods, shiGoods, k)) {
maxL = li - 1;
} else {
minL = li + 1;
}
}
System.out.println(minL);
}
}
private static boolean candiv(int li, int length, List<Integer> ganGoods, List<Integer> shiGoods, int k) {
int gCarCnt = 0;
int sCarCnt = 0;
int gSum = 0;
int sSum = 0;
if (div(li, ganGoods, k, gCarCnt, gSum)) {
return false;
}
if (div(li, shiGoods, k, sCarCnt, sSum)) {
return false;
}
return true;
}
private static boolean div(int li, List<Integer> goods, int k, int sCarCnt, int sSum) {
for (Integer good : goods) {
if (sSum + good <= li) {
sSum += good;
} else {
if (sCarCnt + 1 == k) {
return true;
} else {
sCarCnt += 1;
sSum = good;
}
}
}
return false;
}
}
相关文章
