解题思路

100 人去划船，男生 m 人、女生 100-m 人，男女不能坐同一条船。三种船：大船 6 人 100 元、中船 3 人 75 元、小船 2 人 60 元。要求男女各自正好坐满、三种船都要租，求总价最低的方案。

思路：枚举船的分配。

1. 枚举大船 D、中船 Z、小船 S 的数量（三种都至少 1 只）
2. 检查：能不能把船分成两部分，一部分装男生正好 m 人，另一部分装女生正好 100-m 人
3. 能分的话算总价，记录总价最低的方案

怎么检查男女分船？ 枚举给男生的大船 x 只、中船 y 只、小船 z 只：

• 男生存量 = 6x + 3y + 2z，要正好等于 m
• 女生存量 = 6(D-x) + 3(Z-y) + 2(S-z)，要正好等于 100-m

为什么要正好坐满？ 因为要按最便宜的方案装下所有人，船正好坐满不浪费座位，是经济的选择。

举例：男生 59 人、女生 41 人

• 男生 59 = 9 大船 + 1 中船 + 1 小船（54+3+2）
• 女生 41 = 6 大船 + 1 中船 + 1 小船（36+3+2）
• 总共 15 大船、2 中船、2 小船

参考代码

#include <iostream>
using namespace std;

int main() {
    int m;
    cin >> m;
    int f = 100 - m;

    int bestD = 0, bestZ = 0, bestS = 0, bestC = 1 << 30;

    for (int D = 1; D <= 20; D++) {  // 大船
        for (int Z = 1; Z <= 20; Z++) {  // 中船
            for (int S = 1; S <= 20; S++) {  // 小船
                int cost = D * 100 + Z * 75 + S * 60;
                if (cost >= bestC) continue;

                // 检查男女能否各自正好坐满
                bool ok = false;
                for (int x = 0; x <= D && !ok; x++) {
                    for (int y = 0; y <= Z && !ok; y++) {
                        for (int z = 0; z <= S && !ok; z++) {
                            int boy = 6 * x + 3 * y + 2 * z;
                            int girl = 6 * (D - x) + 3 * (Z - y) + 2 * (S - z);
                            if (boy == m && girl == f) ok = true;
                        }
                    }
                }
                if (ok) {
                    bestC = cost;
                    bestD = D; bestZ = Z; bestS = S;
                }
            }
        }
    }
    cout << bestD << " " << bestZ << " " << bestS << endl;
    return 0;
}

复杂度分析

• 时间复杂度：O(N³)，三重枚举船数
• 空间复杂度：O(1)