（C语言）小船过河代码

﹏ヽ暗。殇╰゛Y 2022-02-02 04:45 202阅读 0赞

【Description】  
一群人划船过河，河边只有一条船，这条船可以容纳两个人，船过河后需要一人将船开回，以便所有人都可以过河，每个人过河速度不一样，两个人过河速度取决于慢的那个人，请问最少需要多久让所有人过河？  
【Input】  
第一行输入人数n；  
第二行输入每个人过河所需的时间；  
【Output】  
输出需要的最少时间  
【Sample Input】  
4  
1 2 5 10  
【Sample Output】  
17  
题目分析：  
两种方法，较容易想到的是第一种方式：  
第一种办法：先让1 2过去（2分钟），1回来（1分钟），1 5过去（5分钟），1回来（1分钟），1 10再过去（10分钟），总共需要19分钟就可以让四个人都过去。

而正确答案是第二种办法：先让1 2过去（2分钟），1回来（1分钟），5 10过去（10分钟），2回来（2分钟），1 2再过去（2分钟），总共需要17分钟就可以让四个人都过去。

本题的关键在于把最慢的和次慢的两个人运过河，因此只要大于四个人的情况下：只需要将这两种方式这两个人运过河的时间做对比：  
第一种：T4+T1+T3+T1  
第二种：T2+T1+T4+T2  
对比之后取短的就行

源码如下：

#include<stdio.h>
    #define N 10
    
    int Time(int *t,int n); 
    int sum=0;
    
    main()
    {
    	int t[N];
    	int n,i,j,k,temp;
    	printf("请输入要过河的人数:");
    	scanf("%d",&n);
    	printf("请输入每个人过河所需的最长时间：");
    	for(i=0;i<n;i++) scanf("%d",&t[i]);
    	
    	for(i=0;i<n-1;i++)
    	  {
    		k=i;
    		for(j=i+1;j<n;j++)	if(t[k]>t[j]) k=j;
    		if(k!=i) {temp=t[i];t[i]=t[k];t[k]=temp;}
    	  }
    
    	Time(t,n);
    	
    	printf("\n%d",sum);
    } 
    
    int Time(int *t,int n)
    {
    	int i;
    	if(n==1) sum=sum+t[0];
    	if(n==2) sum=sum+t[0]+t[1];
    	if(n==3) sum=sum+t[0]+t[1]+t[2];
    	if(n>=4)
    	{
    		if((t[0]+t[2])>(2*t[1])) sum=sum+t[0]+3*t[1]+t[n-1];
    		else sum=sum+2*t[0]+t[1]+t[n-1]+t[n-2];
    	}
    	
    	n=n-2;
    	return sum;
    	Time(t,n);
    }