🌈 🌈 🌈 🌈 🌈 🌈 🌈 🌈 🌈 🌈 🌈 🌈 🌈
 
🍂个人博客首页： KJ.JK
 
💖系列专栏：华为OD机试真题(C++)

一、题目

🔸题目描述

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

🔸输入输出

输入
第一行 length表示供货商数量1 <= length <= 10^4
第二行 goods示供货数数组1 <= goods[j] <= 10^4
第三行 types表示对应货物类型， types[jI等于0或者1， 其中0代表干货,，1代表湿货
第四行k表示单类中转车数量1 <= k <= goods.length
 
输出
运行结果输出一个整数 ，表示中转车统一限载货物数
 
备注
中转车最多跑一趟仓库

🔸样例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 (干货车和湿货车限载最大值) , 是最小的取值

二、题目解析

1、输入供货商数量、供货数数组、 对应货物类型和单类中转车数量。
 
2、求出限制载货量的最小值和最大值，最小值为单个供货商的货物数量，最大值为所有供货商的货物数量之和。
 
3、通过二分答案的方式，不断缩小限制载货量的范围，直到找到最小的限制载货量，使得可以将所有货物装载到中转车上。
 
4、在二分答案的过程中，需要判断当前限制载货量是否可以将所有货物装载到中转车上。具体实现过程如下: .
 
● 维护干货中转车数量、湿货中转车数量 当前干货中转车上已装载的货物总量和当前湿货中转车上已装载的货物总量。
 
● 遍历所有供货商,如果是干货， 则判断当前干货中转车是否还可以装载该供货商的货物，如果可以,则将该货物装载到当前干货中转
转;刮，使用下一辆干货中转车装载该供货商的货物。如果是湿货,则同理。
 
● 如果在遍历完所有供货商后，所有货物都已经成功装载到中转车上，则返回true;否则,返回false。
 
5、输出最小的限制载货量。

三、代码参考

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;struct Goods {int weight; // 货物重量int type; // 货物类型：0表示干货，1表示湿货
};int main() {int n, k;cin >> n;vector<Goods> goods(n);for (int i = 0; i < n; i++) {cin >> goods[i].weight;}for (int i = 0; i < n; i++) {cin >> goods[i].type;}sort(goods.begin(), goods.end(), [](const Goods& a, const Goods& b) {return a.type < b.type; // 按照货物类型从小到大排序});cin >> k;int minLimit = goods.back().weight; // 最小限制量为最重的货物重量int maxLimit = 0;int dryCarSum = 0; // 当前干货中转车上已装载的货物总量int wetCarSum = 0; // 当前湿货中转车上已装载的货物总量for (int i = 0; i < n; i++) {maxLimit += goods[i].weight;}while (minLimit <= maxLimit) {int limit = (minLimit + maxLimit) / 2;int dryCarCount = 0; // 干货中转车数量int wetCarCount = 0; // 湿货中转车数量dryCarSum = 0;wetCarSum = 0;bool canLoad = true;for (int i = 0; i < n; i++) {if (goods[i].type == 0) { // 干货或湿货if (goods[i].weight > limit) { // 当前货物重量超过限制量，无法装载canLoad = false;break;}if (goods[i].type == 0) { // 干货if (dryCarSum + goods[i].weight <= limit) { // 当前干货中转车还可以装载该供货商的货物dryCarSum += goods[i].weight;} else { // 当前干货中转车已经装载到限制量，需要使用下一辆干货中转车if (dryCarCount + 1 == k) { // 已经达到最大干货中转车数量，无法继续装载canLoad = false;break;} else { // 使用下一辆干货中转车装载该供货商的货物dryCarCount += 1;dryCarSum = goods[i].weight;}}} else { // 湿货if (wetCarSum + goods[i].weight <= limit) { // 当前湿货中转车还可以装载该供货商的货物wetCarSum += goods[i].weight;} else { // 当前湿货中转车已经装载到限制量，需要使用下一辆湿货中转车if (wetCarCount + 1 == k) { // 已经达到最大湿货中转车数量，无法继续装载canLoad = false;break;} else { // 使用下一辆湿货中转车装载该供货商的货物wetCarCount += 1;wetCarSum = goods[i].weight;}}}}}if (canLoad) {maxLimit = limit - 1;} else {minLimit = limit + 1;}}cout << minLimit << endl;return 0;
}

作者：KJ.JK

文章对你有所帮助的话，欢迎给个赞或者 star，你的支持是对作者最大的鼓励，不足之处可以在评论区多多指正，交流学习