谜题内容（问题引入）

你或许不止一次见到过这个很有趣味的谜题。
说是啊，唐僧一行四人，来到了一座吊桥左侧，想要最终全部到达吊桥右侧。
但是呢，这个吊桥年久失修，只能同时承载两个人的重量，也就是说，任何时刻，桥上最多只能有2个人。
此外呢，此时已经到了夜晚，位于桥上的人必须要随身携带着火炬才能走路，而他们只有一束火炬。
注意火炬必须通过人为在桥上往返传递，不能直接从吊桥右侧扔到吊桥左侧。
由于行李啊种种原因，他们每个人走路的速度各不相同，孙悟空过桥需要1分钟，沙和尚过桥需要2分钟，猪八戒磨蹭一点，需要5分钟，而唐僧最慢，需要10分钟。
由于只有一束火炬，所以两个人结伴而行的时候，他们的速度要和其中较慢的那一位保持一致。比如用时1分钟的孙悟空，和用时10分钟的唐僧结伴过桥，也得要花费10分钟，即使这肯定让孙悟空非常不耐烦。
现在询问你，想让一行四人最终全部到达吊桥右侧，至少需要多长时间？
大家可以暂停几秒钟，思考一下采取什么样的方案。

谜题答案（对于该样本例子的解决）

相信很多小伙伴都能想到一个总共用时19分钟的方案，这也是最显然、最符合我们直觉的方案。
那就是，既然孙悟空走的那么快，那我为何不让孙悟空来回传递火炬呢？
也就是让孙悟空依次陪每一个人过桥，然后带着火炬快速返回，再陪下一个人过桥。
我们可以计算一下，孙悟空和沙和尚结伴，二人带着火炬过桥，用时2分钟，孙悟空带着火炬返程用时1分钟；
回到吊桥左侧的孙悟空再陪猪八戒过桥，用时5分钟，孙悟空带着火炬返程用时1分钟，
又一次回到吊桥左侧的孙悟空最后再陪唐僧过桥，用时10分钟。
至此，一行四人全部到达吊桥右侧，总共用时为2+1+5+1+10=19分钟。
如果用加号表示从吊桥左侧到右侧，用减号表示从吊桥右侧返回左侧。
从快到慢，孙悟空、沙和尚、猪八戒、唐僧依次编号为1,2,3,4.
那么这种方案可以表述为这样的形式：

$+\{1,2\}-1+\{1,3\}-1+\{1,4\}$

这个方案看上去已经足够迅速了，对吧？那么还有没有更为高效的方案呢？
其实是有的，我们注意到时间瓶颈在于猪八戒和唐僧两人都太慢了，分别要5分钟和10分钟，那么能不能让他俩一起过桥呢？
可是如果猪八戒和唐僧一起过桥后，再让猪八戒带着火炬返回，岂不是要浪费更多的时间吗？
诶，这样想就陷入一个思维误区了，携带火炬返回吊桥左侧的人，并不一定非要是刚刚才到达吊桥右侧的人。
我们可以先让最快的孙悟空和沙和尚结伴过桥，用时2分钟。
再让沙和尚带着火炬返回，用时2分钟。
沙和尚回到吊桥左侧后，猪八戒和唐僧两人接过火炬，结伴过桥，用时10分钟。
两人过桥后，在吊桥右侧等待已久的孙悟空，接过火炬返回，用时1分钟。
最后吊桥左侧仅剩的孙悟空和沙和尚结伴过桥，用时2分钟。
这样算下来，总共用时仅仅为2+2+10+1+2=17分钟！
同样的，新的方案可以表述为：

$+\{1,2\}-2+\{3,4\}-1+\{1,2\}$

实际上，这才是真正最快的方案。
真是非常Amazing啊！

问题推广

表面上看，谜题已经完美解决了。
但是不知道你是否会和我一样，感到如果仅仅止步于此，总觉得少了点什么？
如果每个人的速度数值变动一下，还可以无脑采取这样的方案吗？会不会一开始最符合直觉的方案反而更优秀了呢？
如果不是4个人，而是5个人、6个人...N个人，又该如何思考呢？
行动过程中，每个人既可能在吊桥左侧、也可能在吊桥，仅仅是考虑每个人的位置状态，就有 2^N 种不同的状态，枚举所需要的成本可是指数级别增长的啊！
我们能不能在数学上建立一个模型、设计一个策略，使得不论有多少人、每个人的速度是多少，我们都有办法较为容易地计算出最少用时呢？

方便起见，我们把所有人按照速度从快到慢排序并编号

$0<t_1\le t_2\le\cdots\le t_N$

如果不超过2个人，非常方便，直接一次性全部过桥，写出来是

$+\{1,2\}$

如果有3个人，也很简单，只需要速度最快的人返程1次，也就是

$+\{1,2\}-1+\{1,3\}$

过桥规律1

想要解决 N>=4 时的情况，我们可以先观察观察解决方案有着什么样的基本规律。
首先可以注意到的是，每次都是两个人结伴过桥、然后一个人返回。
可以设想一下，如果 a 单独从吊桥左侧到右侧，那么这必不可能是第一步行动，否则接下来又只能乖乖让 a 带着火炬回来，没有任何意义。

$+a-a\Rightarrow \varnothing$

既然 a 单独从吊桥左侧到右侧不可能是第一步行动，那么有没有可能这不是 a 第一次过桥呢？
从这式子可以看出，这样也是不划算的

$\cdots -a+\cdots-b+a\cdots\Rightarrow \cdots-b\cdots$

好吧，也就是说如果 a 单独从吊桥左侧到右侧，这只可能是 a 第一次过桥，并且不能是整局方案的第一步行动。但是这样也是不划算的，因为与其让 b 回来把火炬传给 a，还不如当初不要让 b 过桥，改为让 b 的伴侣和 a 一起过桥。

$\cdots +\{b,c\}+\cdots-b+a\cdots\Rightarrow \cdots+\{a,c\}\cdots$

同样的方法，也可以证明没有必要两个人结伴返回。

$\cdots +\{a,x\}-\cdots-\{a,b\}\cdots\Rightarrow \cdots+x-\cdots-b\cdots$

于是我们可以放心地说，每次都是两个人结伴过桥、然后一个人返回，由于总人数是 N，那么就是 N-1 次去程和 N-2 次返程。

过桥规律2

为了方便观察，我们可以在纸上画 N 个节点，分别标记上 1 到 N 表示每个编号的人，每个点 i 都对应着一个权值 $t_i$，表示他单独过桥花费的时间。如果两个人结伴过桥，就在他俩对应的节点之间连一条边，注意两个人或许会不止一次结伴过桥，所以这里的边是可以重复叠加的。
只要数一数一个节点 i 连接了多少条边（也就是这个节点的度数 $d_i$），就可以很容易的知道，第 i 个人从吊桥左侧到右侧去了 $d_i$ 次，相应的，从吊桥右侧到左侧单独返回了 $d_i-1$ 次。
由于每个人最终都要过桥，所以每个节点至少连接了一条边，也就是度数至少为1。

$d_i\ge 1$

根据此前的结论，我们知道一共有 N-1 次去程，所以图中一共有 N-1 条边，我们给每条边也赋予一个权值，表示二人结伴过桥花费的时间，也就是这条边所连接的两个点和的权值最大值。
现在我们知道，从吊桥左侧到右侧，花费的总时间为 N-1 条边的边权之和。
从吊桥右侧到左侧返程，花费的总时间，为每个人单独返程的总时间之和。而每个人单独返程的总时间，就是他的点权乘以返程次数（度数减1）。

$\sum_{i=1}^N(d_i-1)t_i+\sum_{ij\in E}\max(t_i,t_j)$

进一步考虑到，每增加一条边，就会分别让连接的两个节点的度数增加1，那么就可以化为这样的形式

$-\sum_{i=1}^N t_i+\sum_{ij\in E}\max(t_i,t_j)+t_i+t_j$

式子的前一项是一个定值，只需要考虑如何让后一项尽可能小。
现在我们已经知道每一条边具体会产生多大的时间代价，那么怎么连接这 N-1 条边呢。
小伙伴可以在纸上画一画，把玩把玩，你会很清晰的发现这样一些规律。
首先，边不可能“交叉”，意思是，如果 $i<j<k<l$，那么 i 连接 k 而 j 连接 l 的情形是不可能出现的。
其次，重复的连边只发生发生在节点 1 和节点 2 之间，并且只有节点 1 有权利和多个不同的节点连边。提示一下，如果不这样做，你会发现改为连接到节点1 或 节点 2 总是会产生更优秀的方案。具体的严谨证明就留给小伙伴们思考了。
以 N=10 的情况为例，最终形成的图一定是类似于这样的结构：

其实啊，这正是最初我们所说的两种方案的结合。
观察图中右侧的那些边（10和9、8和7、6和5），为了避免因为较慢的那些人们分别过桥而产生瓶颈，我们让较慢的人们两两结伴过桥，让最快的1号和2号充当劳模，来回传递火炬。这样的代价是，每有两个慢人结伴过桥，1号和2号也要多一次结伴而行。如果有 k 次满人结伴过桥，那么节点1和节点2之间就要连接 k+1 条边。
观察图中中间的那些变（4和1，3和1），到某个时刻，当较慢的人们渐渐到了吊桥右侧，对于吊桥左侧剩下的人们，即使让1号依次分别带他们过桥，然后1号单独回来传递火炬，也不会浪费太多时间，比他们两两结伴过桥的效果还要好（毕竟不需要1号和2号额外结伴过桥了）。

结论

到此为止，我们可以得出结论，对于 N>=4 的情况，我们只需要考虑最慢的两个人 N 和 N-1 是结伴过桥？还是分别让1号带领他们。
如果结伴过桥，就需要1号和2号先过去，2号回来，N号和N-1号过去，1号回来。这样以来，吊桥左侧就只剩下1至N-2号了，花费时间为

$t_1+2t_2+t_N$

如果分别让1号带领，同样想要达到吊桥左侧只剩下1至N-2号的局面，就需要1号返程两次，花费时间为

$2t_1+t_{N-1}+t_N$

我们只需要在这两个式子之间选择较小的那个，采取对应的策略，就可以将 N 个人的局面转换成 N-2 个人的局面，然后对新的 N 采取同样的决策方法。
注意到，比较这两个式子的本质，是比较 $2t_2-t_1$ 和 $t_N-1$，而序列 t 是已经排好序的。所以一旦我们决定选择让1号依次带领过桥，自此以后就不再需要决策了，统统让1号依次带领过桥就好。

$2t_2-t_1 - t_{N-1}\le 0?$

当然，这个递归形式可以归纳出来，我们本质是枚举有 k 对最慢的人结伴过桥，其中的 k 从 0 到 N/2-1，剩下的人让1号依次带领过桥。
对应的时间代价为

$C_k=(N-2-k)t_1+(2k+1)t_2+\sum_{i=3}^N t_i-\sum_{i=1}^k t_{2N+1-2i}$

对此的解释是，从3号到N号，这N-2个人中如果全部让1号带领过桥，需要1号单独返程N-2次，如果有 k 对最慢的人结伴过桥，1号可以少单独过桥 k 次，所以是 $(N-2-k)t_1$。
相对应的，2号和1号结伴过桥 k+1 次，2号单独返程 k 次，所以是 $(2k+1)t_2$。
从3号到N号，原本都要依次被1号带领，因此从吊桥左侧到右侧而产生的时间代价为 $t_3+...+t_N$，如果有 k 对最慢的人结伴过桥，可以省掉 $t_N-1,t_N-3,...,t_{N-2k+1}$ 作为瓶颈的时间代价，所以是前者减去后者。
好了，至此，我们可以得出最终答案的准确形式

$\min_{k=1}^{\lfloor N/2\rfloor-1}C_k$

其中 $$C_k=(N-2-k)t_1+(2k+1)t_2+\sum_{i=3}^N t_i-\sum_{i=1}^k t_{2N+1-2i}$$