题目来源：Crossing River

A group of N people wishes to go across a river with only one boat, which can at most carry two persons. Therefore some sort of shuttle arrangement must be arranged in order to row the boat back and forth so that all people may cross. Each person has a different rowing speed; the speed of a couple is determined by the speed of the slower one. Your job is to determine a strategy that minimizes the time for these people to get across.
Input
The first line of the input contains a single integer T (1 <= T <= 20), the number of test cases. Then T cases follow. The first line of each case contains N, and the second line contains N integers giving the time for each people to cross the river. Each case is preceded by a blank line. There won’t be more than 1000 people and nobody takes more than 100 seconds to cross.
Output
For each test case, print a line containing the total number of seconds required for all the N people to cross the river.
Sample Input
1
4
1 2 5 10
Sample Output
17

思路：
之前比赛做到过这一题，当时两分钟就做出来了，然而学长把这道题给删了，说的是题目数据出错了；今天按照之前的思路做了一遍，果然连最初的样例都过不了；假设现在有四个人，让他们最短时间过河有两种思路：
（四个人时间从小往大排序fast 1，fast 2,fast 3,fast 4）

• 让fast 1，fast 4过河，fast 1回来； fast 1， fast 3过河，fast 1回来；最后fast1 ， fast 2一起过河；
• 让fast 1，fast 2一起过河，fast 1回来；fast 3 ，fast 4过河 ，fast 2回来；fast1 fast 1一起过河；

每次往对岸运送两个人的时候，都按着两种方法算出来时间，取最小的时间；
当人数小于四，就直接计算。

#include <iostream>
#include <cmath>
#include <map>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxx=1e5+7;
int a[maxx];
int main()
{
int t ;
cin >>t;
while(t--)
{
int n;
cin >>n;
for(int i=1;i<=n;i++)
{
cin >>a[i];
}
sort(a+1,a+n+1);
int sum=0,ans=0;
while(n)
{
if(n==1)
{
sum+=a[1];
n-=1;
}
else if(n==3)
{
sum+=a[1]+a[3]+a[2];
n-=3;
}
else if(n==2)
{
sum+=a[2];
n-=2;
}
else
{
ans=min(a[1]+2*a[2]+a[n],a[n]+a[n-1]+2*a[1]);
sum+=ans;
n-=2;
}
}
cout <<sum<<endl;
}
return 0;
}
//6
//1 2 5 10 12 14

.
.
.

原因

下面解释一下为什么这两种策略是最优的；（转自https://blog.csdn.net/qq_36306833/article/details/68941731）

一.首先证明，先送的应该是最慢的两个：
1.如果a1+an−1−2a2<0a1+an−1−2a2<0，那么，就说明，用最小a1a1的分别单独送an−1,anan−1,an优于让an−1和anan−1和an一起过河。那么这样，由于其他的ai(i<n−1)<an−1ai(i<n−1)<an−1，所以，a1+ai(i<n−1)−2a2<0a1+ai(i<n−1)−2a2<0,所以让最小的a1a1分别送所有的人，优于让他们中的任意两个人组合一起过河。所以这种情况下过河的总过程可以看成是，判断最慢的两个人是否应该一起过河，然后再继续判断下一个。
2.如果存在若干个aiai满足a1+ai−2a2>0a1+ai−2a2>0，那么也就是说明，满足这个条件的这些aiai都有一个特点，那就是，让他和任意一个比他大的一起过河，都应该是要优于让最小的分别送他和那个比他大的过河。那现在，我想要说明的是，对于这些满足这个条件的aiai，应该让他们怎么组合，才能得到最优的结果呢：
设：x=2a2−a1x=2a2−a1。
那么，a1≤a2≤…≤ai−1≤x≤ai≤…≤ana1≤a2≤…≤ai−1≤x≤ai≤…≤an
现在，这个x就是一个分界点，x左边的，让a1a1分别送最好，x右边的，任意两个组合都比这两个单独让a1a1送要快。我假设，让ai和anai和an一起，aj和an−1aj和an−1一起，那么他们的时间花费为：an−1+anan−1+an。而如果我让an−1和anan−1和an一起，ai和ajai和aj一起，那么现在该策略的花费为：an+an+max{ai,ajai,aj}≤an−1+anan−1+an。由此我们的出结论，让an−1和anan−1和an在一起一定优于让他们分别和其他的任意一个组合一起过河。
二.然后下面我们来证明，为什么如果要用最快的两个人帮助运送其他的人：
如果单独过，显然让最快的a1a1来送，这个就不用说了。然后要说明的是：如果是要送的两个人要一起坐船更优，那么也显然是借用最快的a1,a2a1,a2来进行船的调度最快。用类似的方法设用ai,ajai,aj进行船的调度，然后可以证明该选法不会比选a1,a2a1,a2更好（只会更惨）。同时，选用a1,a2a1,a2也可以使得2a2−a12a2−a1也就是x的值尽可能的低，这样也就能让更多的ai可以选择与其他更慢的一起走了ai可以选择与其他更慢的一起走了
综合上面所述，我们证明了“xcx的贪心策略”的正确性，同时，我们还发现，可以对该策略进行改新。下面推出改进后的“xcx的贪心策略2.0”:
每次判断最慢的两个一起运是不是要比分别由最快的送要快，如果是，让这两个一起过去，然后在继续判断，直到某一次，发现，用最快的分别运要更快，然后之后所有的，都让最快的分别一个一个的运。

最后

以上就是称心摩托为你收集整理的Crossing River（poj 1700）原因的全部内容，希望文章能够帮你解决Crossing River（poj 1700）原因所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。