• <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 閱讀(3108) 評論(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综合影院|
久久久久久精品免费看SSS|
亚洲国产成人久久综合野外|
亚洲国产小视频精品久久久三级
|
青春久久|
香蕉久久夜色精品国产2020|
青青草原精品99久久精品66|
久久这里只有精品久久|
亚洲欧美日韩精品久久亚洲区|
久久久久免费看成人影片|
久久精品亚洲乱码伦伦中文|
精品久久久久中文字幕日本|
中文字幕一区二区三区久久网站
|
国产精品热久久无码av|
久久无码AV一区二区三区|
久久精品国产99国产精品澳门|
国産精品久久久久久久|
7777久久久国产精品消防器材
|
久久久免费精品re6|
久久精品这里只有精99品|
国产亚洲精久久久久久无码|
久久婷婷五月综合国产尤物app
|
7777精品久久久大香线蕉|
国内精品伊人久久久久网站|
九九精品99久久久香蕉|
亚洲综合久久久|
久久综合精品国产一区二区三区|
国产精品岛国久久久久|
亚洲va久久久噜噜噜久久狠狠
|
久久e热在这里只有国产中文精品99|
99久久人妻无码精品系列|
久久99国产精品二区不卡|
欧美性大战久久久久久|
久久精品国产亚洲5555|
一本大道加勒比久久综合|
久久精品嫩草影院|
中文字幕亚洲综合久久|
国产成人精品久久一区二区三区av|
国产精品久久久久影院色|
久久成人国产精品二三区|