• <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>

    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>

            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>
            

    
            

            




            







												


        


            


            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 閱讀(3123) 評論(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
			
            
			
            
				分析得很透徹。贊  回復  更多評論
				  
			
            
		

            




            






            

				

            


    
    







            
	   
	



久久久91人妻无码精品蜜桃HD|
亚洲精品乱码久久久久久蜜桃不卡
|
久久免费视频网站|
国产精品成人无码久久久久久
|
一个色综合久久|
精品一区二区久久|
久久久国产精华液|
精品久久人人做人人爽综合|
波多野结衣AV无码久久一区|
一级做a爰片久久毛片人呢|
国产精品久久久久久五月尺|
久久线看观看精品香蕉国产|
国产成人无码精品久久久性色|
色成年激情久久综合|
亚洲国产精品一区二区久久hs|
久久国产成人午夜AV影院|
久久99精品久久只有精品|
2021国内精品久久久久久影院|
51久久夜色精品国产|
久久久久高潮毛片免费全部播放
|
久久亚洲精品无码AV红樱桃|
久久久久女教师免费一区|
久久综合丝袜日本网|
久久99精品久久久久久动态图
|
欧美牲交A欧牲交aⅴ久久
|
久久久久久午夜成人影院
|
久久久久免费精品国产|
少妇久久久久久久久久|
精品国产日韩久久亚洲|
青青青青久久精品国产h久久精品五福影院1421
|
久久久久国产日韩精品网站|
一级做a爱片久久毛片|
A级毛片无码久久精品免费|
久久精品人人做人人爽电影蜜月|
色天使久久综合网天天|
欧美精品九九99久久在观看|
午夜精品久久久久9999高清|
伊人色综合久久天天人守人婷
|
久久精品国产精品亚洲精品|
成人综合久久精品色婷婷|
一本久久知道综合久久|