每日一题：两个仓库的最低配送费用问题

两个仓库的最低配送费用问题

一、问题描述

某公司有 2 个仓库（用 A 和 B 表示），需要给 m 个营业网点（m 为偶数）各配送一件货物。每个仓库正好有 m/2 件货物。配送给不同营业网点的费用使用一个二维数组 cost 表示，其中 cost[i] = [Ai, Bi] 表示第 i 个营业网点从 A 仓发货的运费为 Ai，从 B 仓库发货的费用为 Bi。任务是计算 m 件货物配送的最低费用，要求每个营业网点都有一件货物送到。

二、解题思路

（一）初始假设

若全部从仓库 A 发货，则总费用为 (\sum_{i=1}^{m} A_i)。

（二）差值定义

将第 i 个网点改为从 B 发货，相当于在全部发自 A 的基准上“多花” (\Delta_i = B_i - A_i) 的费用。

（三）选择最优

需要有且仅有 m/2 件货物由 B 发货。为了使额外总费用最小，应当选取最小的 m/2 个 (\Delta_i)（即最负或最小的那些差值）去改由 B 发货。

（四）计算答案

1. 计算全部从 A 发货的初始费用。
2. 计算每个网点从 B 发货相对于从 A 发货的差值。
3. 对差值进行排序，选择最小的 m/2 个差值对应的网点从 B 发货。
4. 将这些最小差值累加到初始费用上，得到最终的最低总费用。

三、代码实现

#include <bits/stdc++.h> // 包含了 C++ 标准库中的大部分头文件，方便使用各种功能
using namespace std;     // 使用标准命名空间，避免每次调用标准库函数或对象时都要加 std::int main() {int m; // 定义变量 m，表示营业网点的数量cin >> m; // 从标准输入读取 m 的值string line; // 定义一个字符串变量 line，用于存储输入的数组字符串// 读取第二行的数组字符串getline(cin, line); // 读取并丢弃之前读取 m 后的换行符getline(cin, line); // 真正读取包含成本数据的行vector<pair<int, int>> cost; // 定义一个向量，用于存储每个营业网点从 A 和 B 仓库发货的费用vector<int> nums; // 定义一个向量，用于存储从输入字符串中提取的所有整数int num = 0; // 定义一个变量 num，用于临时存储当前正在解析的数字bool inNum = false; // 定义一个布尔变量 inNum，用于标记是否正在解析一个数字// 遍历输入的字符串，提取所有整数for (char c : line) { // 遍历字符串中的每个字符if (isdigit(c)) { // 如果当前字符是数字num = num * 10 + (c - '0'); // 将当前字符转换为数字并累加到 num 中inNum = true; // 标记正在解析一个数字} else if (inNum) { // 如果当前字符不是数字，但之前正在解析一个数字nums.push_back(num); // 将解析完成的数字存储到 nums 向量中num = 0; // 重置 num 为 0，准备解析下一个数字inNum = false; // 重置 inNum 为 false，表示当前不再解析数字}}if (inNum) nums.push_back(num); // 如果字符串末尾是一个数字，将其存储到 nums 向量中// 两两配对成 cost[i]for (int i = 0; i < nums.size(); i += 2) { // 遍历 nums 向量，每次跳过两个元素cost.emplace_back(nums[i], nums[i + 1]); // 将每两个连续的数字作为一对，存储到 cost 向量中}// 1. 计算全部从 A 发货的初始费用long long sumA = 0; // 定义一个变量 sumA，用于存储全部从 A 发货的总费用for (auto &p : cost) { // 遍历 cost 向量sumA += p.first; // 将每个营业网点从 A 仓库发货的费用累加到 sumA 中}// 2. 计算差值数组 Δ[i] = B_i - A_ivector<int> diff; // 定义一个向量，用于存储每个营业网点从 B 发货相对于从 A 发货的差值for (auto &p : cost) { // 遍历 cost 向量diff.push_back(p.second - p.first); // 计算差值并存储到 diff 向量中}// 3. 对差值排序，取最小的 m/2 个sort(diff.begin(), diff.end()); // 对 diff 向量进行升序排序long long extra = 0; // 定义一个变量 extra，用于存储额外的费用for (int i = 0; i < m / 2; ++i) { // 遍历 diff 向量的前 m/2 个元素extra += diff[i]; // 将最小的 m/2 个差值累加到 extra 中}// 4. 输出最小总费用cout << (sumA + extra) << endl; // 将初始费用 sumA 和额外费用 extra 相加，输出最终的最低总费用return 0; // 程序正常结束，返回 0
}

四、代码分析

（一）输入处理

• 使用 getline 读取包含成本数据的行，并通过逐字符判断来提取其中的数字，将其存入 nums 向量。
• 然后将 nums 中的数字两两配对，形成 cost 向量，其中每个元素是一个包含两个整数的 pair，分别表示从 A 仓库和 B 仓库发货到对应营业网点的费用。

（二）初始费用计算

• 遍历 cost 向量，将每个网点从 A 仓库发货的费用累加，得到全部从 A 发货的初始总费用 sumA。

（三）差值计算与排序

• 遍历 cost 向量，计算每个网点从 B 仓库发货相对于从 A 仓库发货的差值，并将这些差值存入 diff 向量。
• 对 diff 向量进行排序，以便后续选择最小的 m/2 个差值。

（四）选择最小差值并计算额外费用

• 遍历排序后的 diff 向量的前 m/2 个元素，将这些最小差值累加到 extra 中，extra 表示从 A 仓库发货改为从 B 仓库发货带来的额外费用。

（五）输出结果

• 将初始费用 sumA 与额外费用 extra 相加，得到最终的最低总费用，并输出。

五、总结

本题通过巧妙地利用差值和排序，将问题转化为选择最小的 m/2 个差值来最小化额外费用，从而高效地求解出最低配送费用。这种方法不仅思路清晰，而且时间复杂度较低，适合处理大规模数据。