The Fourth Dimension Space

枯叶北风寒,忽然年以残,念往昔,语默心酸。二十光阴无一物,韶光贱,寐难安; 不畏形影单,道途阻且慢,哪曲折,如渡飞湍。斩浪劈波酬壮志,同把酒,共言欢! -如梦令

POJ 1700-过河问题 经典智力题

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

解题思路:
当人数等于1,2,3的时候:答案很容易得出;
当人数大于等于4时:

若设过桥速度最快的那个人过桥时间为a,第二快为b;过桥第二慢的那个人过桥时间为y,最慢为z;
此时有两种过桥方案:
一.最快和次快的人先过,然后最快的回来,然后最慢与次慢的人再过,次快的回来;
二.最快的和最慢的过,快的回来,在和次慢的过,快的再回来;

第一种方法时间为b*2+a+z
第二种方法时间为y+z+2*a
如果第一种大于第二种 有2*b+a+z>y+z+2*a
化简得
2*b>y+a;
此时只要比较2*b和a+y的大小即可知道那种方法更优 O(∩_∩)O~ 编程解决即可
#include<iostream>
#include
<algorithm>
#include
<numeric>
using namespace std;


int a[1000];

int main()
{
    
int testcase;
    
int n;
    
int i;
    
int j;
    
int sum=0;
    scanf(
"%d",&testcase);
    
for(j=1;j<=testcase;j++)
    
{
        sum
=0;
        scanf(
"%d",&n);
        
for(i=1;i<=n;i++)
            scanf(
"%d",&a[i]);
        sort(a
+1,a+1+n);
        
while(n)
        
{
            
            
if(n==1)
            
{
                sum
+=a[1];
                n
=0;
            }

            
else if(n==2)
            
{
                sum
+=a[2];
                n
=0;
            }

            
else if(n==3)
            
{
                
                sum
+=(a[2]+a[3]+a[1]);
                n
=0;
            }

            
else if(n>=4)
            
{
                
                
                
if(2*a[2]>a[1]+a[n-1])
                
{
                    sum
+=(a[n-1]+a[n])+2*a[1];
                    n
-=2;
                }

                
                
else
                
{
                    sum
+=(a[2]+a[1]+a[n]+a[2]);
                    n
-=2;
                }

            }

            
            
        }

        printf(
"%d\n",sum);
    }

    system(
"pause");
    
return 0;
    
}




说句题外话,据说去年南大保研的面试题就是这道题,一模一样,呵呵 只可惜我还没到保研的时间。。。

posted on 2009-03-28 22:58 abilitytao 阅读(2767) 评论(10)  编辑 收藏 引用

评论

# re: POJ 1700-过河问题 经典智力题 2009-03-29 01:03 陈梓瀚(vczh)

将每一种分布式为节点,节点之间的边权重是时间,作用是人的转移。然后求最短路径。  回复  更多评论   

# re: POJ 1700-过河问题 经典智力题[未登录] 2009-03-29 13:44 abilitytao

@陈梓瀚(vczh)
能否说得再具体一些呢?
虽然最短路算法Dij和floyd我也比较熟 但是我觉得这样做貌似有些困难  回复  更多评论   

# re: POJ 1700-过河问题 经典智力题 2009-03-29 14:58 funcoding

多谢LZ分享...
LZ代码一点注释都没的,还好这个比较短...
但是时间久了,还是会忘了某些变量的含义...
希望能养成习惯...  回复  更多评论   

# re: POJ 1700-过河问题 经典智力题[未登录] 2009-03-29 15:05 abilitytao

@funcoding
我已经把思路写得很清楚了丫 :-)
  回复  更多评论   

# re: POJ 1700-过河问题 经典智力题[未登录] 2009-03-29 15:30 abilitytao

@funcoding
不过还是要谢谢您的提醒 以后我会注意一下
  回复  更多评论   

# re: POJ 1700-过河问题 经典智力题[未登录] 2009-04-04 15:29 菜鸟

用第二种方法 就是:
“二.最快的和最慢的过,快的回来,在和次慢的过,快的再回来;”
“第二种方法时间为y+z+2*a”
是怎么过去的呢???

az先过 a回来
ay过 a回来
ab过

时间是 :z+a+y+a+b = z+y+2*a+b啊
怎么变成 z+y+2*a 了呢?


  回复  更多评论   

# re: POJ 1700-过河问题 经典智力题[未登录] 2009-04-04 15:32 菜鸟

就是好象最后b还没有过去,就结束过河了……  回复  更多评论   

# re: POJ 1700-过河问题 经典智力题[未登录] 2009-04-04 16:42 菜鸟

知道了…………
还是谢谢你……

  回复  更多评论   

# re: POJ 1700-过河问题 经典智力题 2009-04-04 17:05 abilitytao

@菜鸟
你没看懂我的意思 其实以上的分析给出的是每一步的决策
是一个循环,你没有注意到while(n)这个循环语句吗?
当剩下的人数不断变化的时候,我们要根据人数的情况做相应的决策。
并不是一次就全都过去了丫:-)  回复  更多评论   

# re: POJ 1700-过河问题 经典智力题 2009-07-31 12:41 Linz

分析得很透彻。赞  回复  更多评论   


只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理