C语言经典题目

题目
有N个人想要用一条每次只能坐两人的船过河，因此，需要合理的安排来、回以使所有的人都能顺利过河。每个人过河的速度不同，两个人速度取决于速度较慢的一个。你的任务就是想一个策略让所有的人在最短的时间内均过河。

要求 ：时间限制：1000MS 内存限制：10000KB
通过次数（Accepted）：3 提交次数（Submit）：24

说明：
输入
第一行是一个表示测试用例次数的整数T（1<=T<=20），接下来是T个测试用例。每个测试用例的第一行是一个整数N，第二行包含N个整数代表每个人过河的时间。不会超过1000个人（即N<=1000）并且每个人的过河时间不会超过100秒。

输出
每一个测试用例，输出N个人过河所用的最短总时间。

输入示例
1
4
1 5 2 10

输出示例
17
求代码… 哪位高手有的。往赐教 ……

1.正确的算法:
如果n=3, 过河时间为A+B+C
如果n<=2, 好算, 不费口舌了

如果n>=4, 这个是重点:
每次优先考虑把最慢两人送过河
把n人中最快两人记为A,B, 最慢两人记为C,D(过河时间A<B<C<D), n人问题实质上转换为4人过河问题, 参考到4人过河时的优化,
记AB过河, A回, CD过河, B回, 为方法X, 实质是利用最快两人进行优化, 耗时A+2B+D
记AD过河, A回, AC过河, A回, 为方法y, 实质是利用最快一人来过河, 耗时2A+C+D
每次比较这两个方法, 如果x快, 使用x方法, 如果y快, 则用y, 并且, 一旦某次使用y方法后, 以后都不用比较了, 全部使用y方法过河

2.算法正确性证明:
为什么每次先让最慢两人过河? 因为他们迟早要过河...早过晚过一样, 而晚过的话, 有可能时间不能被优化, 所以选择最先过
为什么是两人, 不是三人? 因为这船一次只能两人, 三人问题和两人问题的优化一样, 所以一次考虑三人毫无意义, 同理, 三人以上不加考虑

为什么某次用y过河后不用再比较xy了?
先看这个例子:

1 99 100 101
用x方法是99+1+101+99= 300
y方法是 101+1+100+1 = 203

y比x快的原因是2A+C+D < A+2B+D, 即 A+C<2B
容易想到, 从此以后A+C都会小于2B了(因为C越来越小)

3.补充:
算法分析就到这里了, 至于具体的程序...楼主既然是ACMer, 这个应该不困难
当然, 如果楼主需要的话, 也可以给出程序

最短时间是这样的
以本例子说
最快2人过 时间2
最快人回 时间1
最慢2人过 时间10
最快人回 时间2
最快2人过 时间2
一共17
算法就是这样过河以最快2人和最慢2人交替进行，回来时候都是对岸最快的人回来。