最快过桥问题

电玩女神 2022-05-12 15:16 198阅读 0赞

转载：[经典过桥问题证明][Link 1]

在漆黑的夜里，四位旅行者来到了一座狭窄而且没有护栏的桥边。如果不借助手电筒的话，大家是无论如何也不敢过桥去的。不幸的是，四个人一共只带了一只手电筒，而桥窄得只够让两个人同时过。如果各自单独过桥的话，四人所需要的时间分别是1、2、5、8分钟；而如果两人同时过桥，所需要的时间就是走得比较慢的那个人单独行动时所需的时间。问题是，如何设计一个方案，让这四人尽快过桥。

下面直接给出结论，证明过程，见上面的链接文章（我是没咋整明白）。

最佳方案构造：以下是构造N个人(N≥1)过桥最佳方案的方法：  
1) 如果N=1、2，所有人直接过桥。  
2) 如果N=3，由最快的人往返一次把其他两人送过河。  
3) 如果N≥4，设A、B为走得最快和次快的旅行者，过桥所需时间分别为a、b；  
 而Z、Y为走得最慢和次慢的旅行者，过桥所需时间分别为z、y。那么  
 当2b＞a+y时，使用模式一将Z和Y移动过桥；  
 当2b＜a+y时，使用模式二将Z和Y移动过桥；  
 当2b＝a+y时，使用模式一将Z和Y移动过桥。

模式一：用a把z送过去，a回来。再用a把y送过去，a再回来。（time1=z+a+y+a）

模式二：a,b先过去。a回来。y,z过去，b回来。(time2=b+a+z+b)

mintime=min(time1,time2);//这也是上面得出的不等式。

> 一是最快带最慢两人，即过桥情况是ay、a、az和a，先把y和z先送过；
> 
>   二是最快和次快的带最慢和次慢，即过桥的情况是ab、a、yz和b，先把y和z先送过；
> 
>   这两种情况所花的时间有所不同，尽量选时间短的方案；
> 
> ————————————[https://blog.csdn.net/tigerisland45/article/details/79276181][https_blog.csdn.net_tigerisland45_article_details_79276181]

题目：POJ2573 ZOJ1877 Bridge

## Description ##

n people wish to cross a bridge at night. A group of at most two people may cross at any time, and each group must have a flashlight. Only one flashlight is available among the n people, so some sort of shuttle arrangement must be arranged in order to return the flashlight so that more people may cross.  
Each person has a different crossing speed; the speed of a group is determined by the speed of the slower member. Your job is to determine a strategy that gets all n people across the bridge in the minimum time.

## Input ##

The first line of input contains n, followed by n lines giving the crossing times for each of the people. There are not more than 1000 people and nobody takes more than 100 seconds to cross the bridge.

## Output ##

The first line of output must contain the total number of seconds required for all n people to cross the bridge. The following lines give a strategy for achieving this time. Each line contains either one or two integers, indicating which person or people form the next group to cross. (Each person is indicated by the crossing time specified in the input. Although many people may have the same crossing time the ambiguity is of no consequence.) Note that the crossings alternate directions, as it is necessary to return the flashlight so that more may cross. If more than one strategy yields the minimal time, any one will do.

## Sample Input ##

4
    1
    2
    5
    10

## Sample Output ##

17
    1 2
    1
    5 10
    2
    1 2

## 代码： ##

#include <iostream>
    #include <cstdio>
    #include <cstring>
    #include <algorithm>
    using namespace std;
    int num[1000];
    
    int main()
    {
        int n;
        while(cin>>n)
    	{
            memset(num,0,sizeof(num));
            for(int i=1;i<=n;i++)
                cin>>num[i];
            
            sort(num+1,num+n+1);
            
            if(n==1)
    		{
                printf("%d\n",num[1]);
                printf("%d\n",num[1]);
                continue;
            }
            
            
            //计算最短时间 
            int s=n;
            int ans=0;
            while(s>3)
    		{
                if(num[1]+num[s-1]<2*num[2])
                    ans+=2*num[1]+num[s]+num[s-1];
                else
                        ans+=2*num[2]+num[1]+num[s];
                    s-=2;
            }
            if(s==2)
                ans+=num[2];
    
            if(s==3)
                ans+=num[1]+num[2]+num[3];
    
            printf("%d\n",ans);
            
            
    		
    		//打印步骤 
            while(n>3)
    		{
                if(num[1]+num[n-1]<2*num[2])
                    printf("%d %d\n%d\n%d %d\n%d\n",num[1],num[n],num[1],num[1],num[n-1],num[1]);
                else
                    printf("%d %d\n%d\n%d %d\n%d\n",num[1],num[2],num[1],num[n-1],num[n],num[2]);
                n-=2;
            }
            if(n==2)
                printf("%d %d\n",num[1],num[2]);
            if(n==3)
                printf("%d %d\n%d\n%d %d\n",num[1],num[3],num[1],num[1],num[2]);
        }
        return 0;
    }

[Link 1]: https://blog.csdn.net/kjcsdnblog/article/details/43496719
[https_blog.csdn.net_tigerisland45_article_details_79276181]: https://blog.csdn.net/tigerisland45/article/details/79276181