当前位置:首页 > 题解目录 > 正文内容

【题解】Crossing River

亿万年的星光7个月前 (01-20)题解目录965

【题目描述】

几个人过河,每次过两人一人回,速度由慢者决定,问过河所需最短时间。

【输入描述】

输入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;
}


扫描二维码推送至手机访问。

版权声明:本文由青少年编程知识记录发布,如需转载请注明出处。

分享给朋友:

相关文章

【题解】区间和

1.区间和(sum.cpp)【描述】输入一个整数Q,进行Q次询问,每次给定两个整数l和r,每一次输出l~r中所有平方数的和 % 1000000007【输入】第一行是一个整数Q后面的Q行每行有...

【题解—深搜】马走日

【题解—深搜】马走日

【题目描述】马在中国象棋以日字形规则移动。请编写一段程序,给定n×m大小的棋盘,以及马的初始位置(x,y),要求不能重复经过棋盘上的同一个点,计算马可以有多少途径遍历棋盘上的所有点。【输入】第一行为整...

【题解】直方图

直方图(histogram.cpp)【题目描述】给定一个非负整数数组,统计里面每一个数的出现次数。我们只统计到数组里面最大的数。假设Fmax(Fmax<10000)是数组里最大的数,那么我们只统...

绝对素数

【题目描述】如果一个自然数是素数,且它的数字位置经过对换后仍为素数,则称为绝对素数,例如13。试求出所有二位绝对素数。【输入描述】无【输出描述】所有二位绝对素数(由小到大,一个数一行)。【输入样例】无...

【题解】车厢调度

【题解】车厢调度

【题目描述】有一个火车站,铁路如图所示,每辆火车从A驶入,再从B方向驶出,同时它的车厢可以重新组合。假设从A方向驶来的火车有n节(n<=1000)。分别按照顺序编号为1,2,3,...n。假定在...

【题解】木材加工

【题目描述】 木材厂有一些原木,现在想把这些木头切割成一些长度相同的小段木头(木头有可能有剩余),需要得到的小段的数目是事先给定的,切割时希望得到的小段越长越好。   ...