过桥问题

您所在的位置:网站首页 spring的图标 过桥问题

过桥问题

#过桥问题| 来源: 网络整理| 查看: 265

过桥问题:

问题描述:4个人在晚上过一座小桥,过桥时必须要用到手电筒,只有一枚手电筒,每次最多只可以有两人通过, 4个人的过桥速度分别为1分钟、2分钟、5分钟、10分钟,试问最少需要多长时间4人才可以全部通过小桥?

 

Morewindows的方法(以下参考blog: http://blog.csdn.net/MoreWindows/article/details/7481851)

Morewindows君通过观察发现,要么是最快者将最慢的2个送过桥,要么是最快的2个将最慢的2个送过桥。即将过桥的人按其过桥的时间从小到大排列,设为A,B,…… Y,Z。其中A和B是最快的二个,Y和Z是最慢的二个。那么就有二种方案:

方案一 最快者将最慢的2个送过桥

第一步:A和Z过桥,花费Z分钟。

第二步:A回来,花费A分钟。

第三步:A和Y过桥,花费Y分钟。

第四步:A回来,花费A分钟。

这四步后总人数就减小2个,花费时间为A + A + Y + Z分钟。

方案二 最快的2个将最慢的2个送过桥

第一步:A和B过桥,花费B分钟。

第二步:A回来,花费A分钟。

第三步:Y和Z过桥,花费Z分钟。

第四步:B回来,花费B分钟。

这四步后总人数同样减小2个,花费时间为A + B + B + Z分钟。

这样,每次比较一下这二种方案就能将总人数减小2。然后我们再考虑一些边界情况:

有三个人过桥设为A,B,C(已经排好序,下同)。应该花费A + B + C分钟。

有二个人过桥设为A,B。那么肯定是花费B分钟。

有一个人过桥设为A。肯定花费A分钟。

上述方法并没有证明其正确性,只不过在实际中可用。

接着自己实现代码如下:

#include using namespace std; #define maxn 1001 int f1(const void *a,const void *b) { return *(int *)a-*(int *)b; } void f(int *A,int n,int &count) { if(n==3) { count+=A[0]+A[1]+A[2]; return ; } if(n==2) { count+=A[1]; return ; } int temp1=2*A[0]+A[n-1]+A[n-2]; int temp2=A[0]+2*A[1]+A[n-1]; count+=temp1>=temp2?temp2:temp1; n=n-2; f(A,n,count); return ; } int main() { int count; int N,A[maxn]; while(cin>>N) { count=0; memset(A,0,sizeof(A)); for(int i=0; i>A[i]; qsort(A,N,sizeof(int),f1); f(A,N,count); cout


【本文地址】


今日新闻


推荐新闻


CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3