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

            




            






            

				

            


    
    







            
	   
	



精品精品国产自在久久高清|
亚洲午夜久久久久妓女影院|
久久国产乱子伦精品免费强|
久久福利青草精品资源站|
国产精品欧美久久久久天天影视|
国产成人久久精品麻豆一区|
久久无码国产|
久久久久人妻精品一区二区三区
|
久久青青草原亚洲av无码|
久久婷婷是五月综合色狠狠|
亚洲综合熟女久久久30p|
日韩精品久久久久久|
色欲久久久天天天综合网|
51久久夜色精品国产|
伊人色综合久久天天人守人婷|
AV色综合久久天堂AV色综合在|
久久免费大片|
国产亚洲色婷婷久久99精品91|
亚洲成色WWW久久网站|
久久精品国产一区二区三区|
狠狠色丁香久久综合婷婷|
久久精品国产亚洲AV忘忧草18|
激情综合色综合久久综合|
国内精品久久久久影院一蜜桃|
蜜桃麻豆WWW久久囤产精品|
成人精品一区二区久久久|
国内精品久久久久|
久久亚洲精精品中文字幕|
99久久夜色精品国产网站
|
久久免费视频6|
色综合久久最新中文字幕|
久久精品人人做人人爽97|
99精品久久精品一区二区|
午夜精品久久久久久|
日韩中文久久|
欧美日韩精品久久久免费观看|
久久综合丝袜日本网|
国内精品久久久久久久亚洲|
中文字幕一区二区三区久久网站|
久久精品国产福利国产秒|
91麻精品国产91久久久久|