题解

题目描述

某公司有 $2$ 个仓库（用 $A$ 和 $B$ 表示），需要给 $m$（$m$ 为偶数）个营业网点各配送一件货物。假设每个仓库正好都有 $\tfrac{m}{2}$ 件货物，配送给不同营业网点的费用使用一个二维数组 $\mathit{cost}$ 表示，其中

表示第 $i$ 个营业网点从 $A$ 仓发货的运费为 $A_i$，从 $B$ 仓库发货的费用为 $B_i$。请计算 $m$ 件货物配送的最低费用，要求每个营业网点都有一件货物送到。

思路

1. 初始假设：若全部从仓库 $A$ 发货，则总费用为$$\sum_{i=1}^m A_i.$$
2. 差值定义：将第 $i$ 个网点改为从 $B$ 发货，相当于在全部发自 $A$ 的基准上“多花”$$\Delta_i = B_i - A_i$$ 的费用。
3. 选择最优：需要有且仅有 $\tfrac{m}{2}$ 件货物由 $B$ 发货。为了使额外总费用最小，应当 选取最小的 $\tfrac{m}{2}$ 个 $\Delta_i$（即最负或最小的那些差值）去改由 $B$ 发货。
4. 计算答案：
   

C++

#include <bits/stdc++.h>
using namespace std;

int main() {
    int m;
    cin >> m;
    string line;
    // 读取第二行的数组字符串
    getline(cin, line);           // 读掉行尾
    getline(cin, line);           // 真正的数组行
    vector<pair<int,int>> cost;
    // 提取所有整数
    vector<int> nums;
    int num = 0;
    bool inNum = false;
    for (char c : line) {
        if (isdigit(c)) {
            num = num * 10 + (c - '0');
            inNum = true;
        } else if (inNum) {
            nums.push_back(num);
            num = 0;
            inNum = false;
        }
    }
    if (inNum) nums.push_back(num);
    // 两两配对成 cost[i]
    for (int i = 0; i < nums.size(); i += 2) {
        cost.emplace_back(nums[i], nums[i+1]);
    }

    // 1. 计算全部从 A 发货的初始费用
    long long sumA = 0;
    for (auto &p : cost) {
        sumA += p.first;
    }
    // 2. 计算差值数组 Δ[i] = B_i - A_i
    vector<int> diff;
    for (auto &p : cost) {
        diff.push_back(p.second - p.first);
    }
    // 3. 对差值排序，取最小的 m/2 个
    sort(diff.begin(), diff.end());
    long long extra = 0;
    for (int i = 0; i < m/2; ++i) {
        extra += diff[i];
    }
    // 4. 输出最小总费用
    cout << (sumA + extra) << endl;
    return 0;
}

Python

# -*- coding: utf-8 -*-
import sys

def main():
    # 读取输入
    m = int(sys.stdin.readline().strip())
    line = sys.stdin.readline().strip()
    # 提取所有整数
    nums = []
    num = 0
    in_num = False
    for c in line:
        if c.isdigit():
            num = num * 10 + int(c)
            in_num = True
        elif in_num:
            nums.append(num)
            num = 0
            in_num = False
    if in_num:
        nums.append(num)
    # 构造 cost 列表
    cost = [(nums[i], nums[i+1]) for i in range(0, len(nums), 2)]
    
    # 计算全部从 A 发货的费用
    sumA = sum(a for a, b in cost)
    # 计算差值列表 Δ = B_i - A_i
    diffs = sorted(b - a for a, b in cost)
    # 取最小的 m/2 个差值并累加
    extra = sum(diffs[:m//2])
    # 输出结果
    print(sumA + extra)

if __name__ == "__main__":
    main()

Java

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int m = Integer.parseInt(br.readLine().trim());
        String line = br.readLine().trim();
        
        // 提取所有数字
        List<Integer> nums = new ArrayList<>();
        int num = 0;
        boolean inNum = false;
        for (char c : line.toCharArray()) {
            if (Character.isDigit(c)) {
                num = num * 10 + (c - '0');
                inNum = true;
            } else if (inNum) {
                nums.add(num);
                num = 0;
                inNum = false;
            }
        }
        if (inNum) {
            nums.add(num);
        }
        
        // 构造 cost 列表
        List<int[]> cost = new ArrayList<>();
        for (int i = 0; i < nums.size(); i += 2) {
            cost.add(new int[]{nums.get(i), nums.get(i+1)});
        }
        
        // 计算全部从 A 发货的费用
        long sumA = 0;
        for (int[] p : cost) {
            sumA += p[0];
        }
        // 计算差值列表，并排序
        List<Integer> diffs = new ArrayList<>();
        for (int[] p : cost) {
            diffs.add(p[1] - p[0]);
        }
        Collections.sort(diffs);
        
        // 累加最小的 m/2 个差值
        long extra = 0;
        for (int i = 0; i < m/2; i++) {
            extra += diffs.get(i);
        }
        // 输出最小总费用
        System.out.println(sumA + extra);
    }
}

题目内容

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

输入描述

第一行是一个整数 $M$ ，代表营业网点数量。$2<M<=100$， $M$ 为偶数第二行是一个长度为 $M$ 的二维数组 $cost$ ，其中 $cost[i]=[Ai,Bi]$，$Ai$ 和 $Bi$ 分别表示从 $A、B$ 仓库发货的费用。

$1<=Ai，Bi<=1000$

输出描述

一个整数，表示最低费用

样例1

输入

2
[[10,30],[30,200]]

输出

60

说明

$2$ 个营业网点，每个仓库备有 $1$ 件货物

第 $1$ 个营业网点从 $B$ 发货，费用 $30$

第 $2$ 个营业网点从 $A$ 发货，费用 $30$

样例2

输入

4
[[10,30],[30,200],[300,50],[40,20]]

输出

110

说明

$4$个营业网点，每个仓库有$2$件货物

第 $1$ 个营业网点从 $A$ 发货，费用 $10$

第 $2$ 个营业网点从 $A$ 发货，费用 $30$

第 $3$ 个营业网点从 $B$ 发货，费用 $50$

第 $4$ 个营业网点从 $B$ 发货，费用 $20$