【华为OD机试真题 C++】1054 - 统一限载货物数最小值 | 机试题+算法思路+考点+代码解析

安博电竞

文章目录

- 一、华为货物题目
- - 🔸题目描述
  - 🔸输入输出
  - 🔸样例1
  - 🔸样例2
- 二、机试机试题目解析
- 三、真题代码参考
作者：KJ.JK

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

一、统题算题目

🔸题目描述

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

【华为OD机试真题 C++】1054 - 统一限载货物数最小值 | 机试题+算法思路+考点+代码解析

🔸输入输出

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

🔸样例1

输入43 2 6 30 1 1 02输出6说明货物1和货物4为干货，由2辆干货中转车中转，每辆车运输一个货物，限载为3货物2和货物3为湿货，由2辆湿货中转车中转,每辆车运输一个货物，限载为6这样中转车统一限载货物数可以设置为6 (干货车和湿货车限载最大值)，是最小的取值

🔸样例2

输入43 2 6 80 1 1 11输出16说明货物1为干货，由1辆干货中转车中转，限载为3货物2、货物3、点代货物4为湿货，由1辆湿货中转车中转，限载为16这样中转车统一限载货物数可以设置为16 (干货车和湿货车限载最大值) ,码解是最小的取值

二、题目解析

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

三、代码参考

#include #include #include using namespace std;struct Goods {int weight; // 货物重量int type; // 货物类型：0表示干货，1表示湿货};int main() {int n, k;cin >> n;vector 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;}