【题解】Crossing River
【题目描述】
几个人过河，每次过两人一人回，速度由慢者决定，问过河所需最短时间。
【输入描述】
输入t组数据，每组数据第1行输入n，第2行输入n个数，表示每个人过河的时间。
【输出描述】
输出t行数据，每行1个数，表示每组过河最少时间。
【样例1输入】
1 4 1 2 5 10
【样例1输出】
17
【思路1】基于贪心过程分解
我们考虑
甲1 （最快） 乙2 （次快） 丙5 （次慢） 丁10 （最慢）
第一种方案：甲乙过去（2分钟），甲回来（1分钟），甲丙过去（5分钟），甲回来（1分钟），甲丁过去（10分钟）。总共19分钟
第二种方案：甲乙过去（2分钟），甲回来（1分钟），丙丁过去（10分钟），乙回来（2分钟），甲乙过去（2分钟）。总共17分钟。
1.假设只有一个人 ：那么花费的时间就是这个人所用的时间 time=a[i] 2.假设只有两个人 ：那么花费的时间就是慢的这个人所用的时间 time=max(a[i],a[i+1])
3.假设有三个人 ，举例说明：
方案1：每次最快的先过。甲乙过去（2分钟），甲回来（1分钟），甲丙过去（5 分钟）。共8分钟。 方案2：最快和最慢的先过。甲丙过去（5分钟），甲回来（1分钟），甲乙过去（2 分钟）。共8分钟。 方案5:最慢的先过。乙丙先过（5分钟，）乙回来（2分钟），甲乙过去（2分钟）。共9分钟。
结论：三个人时，方案1和方案2结果是一致的，（实际上是一种方案，因为每次都是时间最少的在来回移动，只是改变了顺序）
过去的时候取最慢的人的速度，回来的时候取最快的人速度。
4.假设有4个人时，举例说明
甲1（最快） 乙2（次快） 丙5 （次慢） 丁8（最慢） 方案1：每次最快的人回来。 甲乙过去（2分钟），甲回来（1分钟），甲丙过去（5分钟），甲回来（1分钟），甲丁过去（8分钟）。总共17分钟 方案2：最快和最慢搭配。 甲乙过去（2分钟），甲回来（1分钟），甲丁过去（8分钟），甲回来（1分钟），甲丙过去（5分钟），共17分钟。 方案3：最慢和次慢搭配。 甲乙过去（2分钟），甲回来（1分钟），丙丁过去（8分钟），乙回来（2分钟），甲乙过去（2分钟）。总共15分钟。 方案4: 每次都是最慢。 丙丁过去（8分钟），丙回来（5分钟），丙乙过去（5分钟），乙回来（2分钟），甲乙过去（2分钟），共25分钟。 可以看出这种方法中，方案1与方案2是同一种。最优方案是方案5，他的关键点是丙丁同时过去。 也就是，是让两个最慢的人同时过桥。方案4明显不成立，保证了最慢的人同时过桥， 但是来回的时间非常长。
如果把数据改成下面这样:
甲1（最快） 乙4（次快） 丙5（次慢） 丁8（最慢） 方案1：每次最快的人回来。 甲乙过去（4分钟），甲回来（1分钟），甲丙过去（5分钟），甲回来（1分钟），甲丁过去（8分钟）。总共19分钟 方案2：最快和最慢搭配。 甲乙过去（4分钟），甲回来（1分钟），甲丁过去（8分钟），甲回来（1分钟），甲丙过去（5分钟），共19分钟。 方案5：最慢和次慢搭配。 甲乙过去（4分钟），甲回来（1分钟），丙丁过去（8分钟），乙回来（4分钟），甲乙过去（4分钟）。总共21分钟。 方案4: 每次都是最慢（更不可能） 可以看出这种方法中，方案1和方案2是同一种方案， 对比与上个样例，这个方案5明显行不通，让两个最慢的一组， 反而更慢了。
区别：
1 2 5 8 和 1 4 5 8 之间的差异:
他们分别为最快，次快，次慢，最慢。 差异在于： 次快的人要不要参与。
数学推导：
假设四个人过河的时间分别是T1，T2，T5，T4，（T1<T2<T5<T4,最快，次块，次慢，最慢）,
上述两个样例最优方案的过河时间分别为
第一种：1 2 5 8 ：T2+T1+T4+T2+T2 （最慢和次慢）
第二种：1 4 5 8： T2+T1+T5+T1+T4 （最快和次快）（最快和最慢）
两者求差：T2+T1+T4+T2+T2 - （T2+T1+T5+T1+T4 ）
=2T2-T5-T1
或者 (T1+T5)-2T2
即：T1+T5 的和 与 2T2的关系。
结论： T1+T5 >2T2 , 采用 第一种，最慢和次慢的要一块
T1+T5 <2T2, 采用第二种， 最快和次快
T1+T5=2T2。 两种方法无差异。
即：过河时间和最快，次快，次慢有关。与其他无关
答案就在两种方案之间，
方案1：每次最快和次快一块（等同于最快和最慢一块）
最快的两人（T1, T2）先过河，然后让第二快的人（T2）返回。 让 T1 和 T2 先过河。 让 T1 返回。 让 Tn 和 Tn-1 过河（两个人中最慢的过河）。 让 T1 返回。 让 T1 和 T2 再次过河。
方案2：最慢和次慢一组（注意先让最快的过去一次）
最快的两人（T1, T2）先过河，然后最快的人（T1）返回接其他人。 让 T1 和 T2 先过河。 让 T1 返回。 让 Tn-1 和 Tn 过河（两个人中最慢的过河）。 让 T2 返回。 让 T1 和 T2 再次过河。
那么min (方案1 ，方案2)即可
贪心策略：如何选择最慢的两个人过河，成为这个题的关键选择。
只要最慢的两个人过去了，剩余部分又可以按照贪心思想继续选人。
【参考答案】
#include<bits/stdc++.h>
using namespace std;
int a[10005];
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+1+n); //由小到大排序
long long sum=0;
//四个人以上的情况
while(n>=4){
int t1=a[1]+a[2]+a[n]+a[2];//方案1
int t2=a[1]+a[n]+a[1]+a[n-1];//方案2：
if(t1<t2){
sum+=t1;
}else{
sum+=t2;
}
n-=2;//每次过去两个
}
//三个人的情况
if(n==3){
sum+=a[1]+a[2]+a[3];
}
if(n==2)sum+=a[2];
cout<<sum<<endl;
}
return 0;
}扫描二维码推送至手机访问。
版权声明：本文由青少年编程知识记录发布，如需转载请注明出处。