题解：P15051 [UOI 2023 II Stage] Nova Poshta

· · 题解

题目主要意思

给定 5 件货物的重量和两辆卡车的载重量，判断能否完成配送，若两车都能单独装完所有货、仅一辆能单独装完、需要两车合作装完或完全装不下，分别输出对应结果，合作的情况需给出任意一种合法的货物分配方案。

思路

先算货物总重，判断单辆卡车能否单独装下并输出对应结果；若不能，二进制枚举所有分给Vasyl的货物组合，验证合法则输出合作方案，无合法组合则输出无法完成。

代码


#include <iostream>
#include <vector>
using namespace std;

int main() {
    // 存储5件货物的重量，下标0-4对应货物1-5
    vector<int> w(5);
    int M1, M2, sum = 0; // M1/Vasyl卡车容量 M2/Petro卡车容量 sum/货物总重量
    // 输入5件货物重量并累加总重
    for (int i = 0; i < 5; i++) {
        cin >> w[i];
        sum += w[i];
    }
    // 输入两辆卡车的载重量
    cin >> M1 >> M2;

    // 判断单辆卡车是否能单独装下所有货物
    bool vasyl_alone = (sum <= M1); // Vasyl单独运输是否可行
    bool petro_alone = (sum <= M2); // Petro单独运输是否可行
    if (vasyl_alone && petro_alone) { // 两人都能单独运输
        cout << "They both can do it!" << endl;
        return 0;
    }
    if (vasyl_alone) { // 仅Vasyl能单独运输
        cout << "Vasyl can do it!" << endl;
        return 0;
    }
    if (petro_alone) { // 仅Petro能单独运输
        cout << "Petro can do it!" << endl;
        return 0;
    }

    // 存储最终分配方案：Vasyl和Petro分别装的货物编号
    vector<int> vas, pet;
    bool find_sol = false; // 标记是否找到合法分配方案
    // 二进制枚举Vasyl的货物组合，mask从1到31（5位二进制，覆盖所有非空组合）
    for (int mask = 1; mask < (1 << 5); mask++) {
        int sum_vas = 0; // 当前组合中Vasyl装载的货物总重
        vector<int> tmp_vas; // 临时存储当前组合的货物编号
        for (int i = 0; i < 5; i++) {
            // 若mask的第i位为1，说明第i+1号货物分给Vasyl
            if (mask & (1 << i)) {
                sum_vas += w[i];
                tmp_vas.push_back(i + 1);
            }
        }
        int sum_pet = sum - sum_vas; // Petro装载的剩余货物总重
        // 验证当前分配是否合法：两人的装载重量都不超过各自卡车容量
        if (sum_vas <= M1 && sum_pet <= M2) {
            vas = tmp_vas; // 保存Vasyl的货物分配
            // 遍历所有货物，将未分给Vasyl的分给Petro
            for (int i = 0; i < 5; i++) {
                if (!(mask & (1 << i))) {
                    pet.push_back(i + 1);
                }
            }
            find_sol = true; // 找到合法方案
            break; // 找到即退出，无需继续枚举
        }
    }

    // 根据是否找到合法方案输出结果
    if (!find_sol) { // 无合法方案，无法完成配送
        cout << "They can not do it!" << endl;
    } else { // 找到合法方案，输出合作结果及分配
        cout << "They need to work together!" << endl;
        cout << "Vasyl: ";
        for (int x : vas) cout << x << " "; // 输出Vasyl的货物编号
        cout << endl;
        cout << "Petro: ";
        for (int x : pet) cout << x << " "; // 输出Petro的货物编号
        cout << endl;
    }
    return 0;
}