过桥问题 |
您所在的位置:网站首页 › spring的图标 › 过桥问题 |
过桥问题: 问题描述: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 |