题解

记所有人过桥时间升序为 $t_1\le t_2\le\cdots\le t_n$，桥容量为 $c$。

核心观察：灯必须往返，只有最快的人能以最小代价带灯回去；过桥时耗时为本次队伍中最慢者。对 $c\ge3$ 与 $c=2$ 情形可分别讨论。

情况一：$c=2$

经典两人桥问题。每轮将两名最慢者送过去并把灯带回，保留 $t_1,t_2$ 在起点作为摆渡人。两种方案：

1. $t_1,t_2$ 过去；$t_1$ 回；两慢者过去；$t_2$ 回，代价 $t_1+2t_2+t_n$。
2. $t_1,t_n$ 过去；$t_1$ 回；$t_1,t_{n-1}$ 过去；$t_1$ 回，代价 $2t_1+t_{n-1}+t_n$。

取较小者，淘汰两名最慢者（$n\gets n-2$）继续。收尾时：

• $n=3$：代价 $t_1+t_2+t_3$；
• $n=2$：代价 $t_2$；
• $n=1$：代价 $t_1$。

情况二：$c\ge3$

此时可以一次带走至少两个最慢者，最佳策略是“最快者单向摆渡”：

• 每轮让 $t_1$ 携带最多的慢者（$c-1$ 个当前最慢者）一起过桥，耗时为本轮最慢 $t_{\text{slow}}$；
• $t_1$ 带灯返回，耗时 $t_1$。

该轮净转移 $c-1$ 人，总花费 $t_{\text{slow}}+t_1$，并保持起点仍有 $t_1$ 以最低成本继续摆渡。任何让更慢的人返回或增加额外摆渡者都会增加费用且不增加已转移人数，因此此策略最优。

循环到剩余人数不超过 $c$ 时，最后一批一起过桥，耗时为剩余人中的最大值（即当前最慢）。

正确性说明

$c=2$

每轮两种方案都将两名最慢者送到终点，并把 $t_1,t_2$ 带回起点，形成相同的子问题规模 $n-2$。任意最优解在这一轮必采取上述两类之一（灯必须回到起点，且最优回程一定由最快者承担）。因此对当前轮选择代价较小的方案并递归，得到全局最优。

$c\ge3$

考虑一轮操作后要使灯回到起点、人数减少。若让除 $t_1$ 外任何人返回，代价不会低于 $t_1$，且不会多带人回来，故回灯人必为 $t_1$。若送出的人不是最多的 $c-1$ 个尚未过桥者，则本轮相同代价下转移人数更少，劣于直接送 $c-1$ 个最慢者。故每轮最优必为“$t_1$ 携 $c-1$ 个当前最慢者过去，$t_1$ 返回”。这形成规模减小 $c-1$ 的同类子问题；最后一批人数 $\le c$ 时直接一次送完即最优。由数学归纳可得全局最优。

复杂度

排序 $O(n\log n)$，随后线性扫描，空间 $O(1)$（除存数组外）。

参考代码

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, c;
    if (!(cin >> n >> c)) return 0;
    vector<int64> t(n);
    for (auto &x : t) cin >> x;
    sort(t.begin(), t.end());
    int64 ans = 0;

    if (c == 2) {
        while (n > 3) {
            // 方案1：t1,t2 去；t1 回；两最慢去；t2 回
            int64 option1 = t[0] + 2 * t[1] + t[n - 1];
            // 方案2：t1,tn 去；t1 回；t1,t(n-1) 去；t1 回
            int64 option2 = 2 * t[0] + t[n - 2] + t[n - 1];
            ans += min(option1, option2);
            n -= 2;
        }
        if (n == 3) ans += t[0] + t[1] + t[2];
        else if (n == 2) ans += t[1];
        else ans += t[0];
    } else {
        int idx = n - 1;
        while (idx + 1 > c) {
            ans += t[0] + t[idx];
            idx -= (c - 1);
        }
        ans += t[idx]; // 剩余人数 ≤ c，一次过
    }

    cout << ans << "\n";
    return 0;
}