• <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
            

            枯葉北風(fēng)寒，忽然年以殘，念往昔，語默心酸。二十光陰無一物，韶光賤，寐難安； 不畏形影單，道途阻且慢，哪曲折，如渡飛湍。斬浪劈波酬壯志，同把酒，共言歡！  -如夢令
            

            




            
	
					
	
            
		
            
			POJ 1700-過河問題 經(jīng)典智力題
		
            
		題目描述：在漆黑的夜里，四位旅行者來到了一座狹窄而且沒有護(hù)欄的橋邊。如果不借助手電筒的話，大家是無論如何也不敢過橋去的。不幸的是，四個人一共只帶了一只手電筒，而橋窄得只夠讓兩個人同時過。如果各自單獨(dú)過橋的話，四人所需要的時間分別是1、2、5、8分鐘；而如果兩人同時過橋，所需要的時間就是走得比較慢的那個人單獨(dú)行動時所需的時間。問題是，如何設(shè)計一個方案，讓這四人盡快過橋。 

            解題思路：
            當(dāng)人數(shù)等于1，2，3的時候：答案很容易得出；
            當(dāng)人數(shù)大于等于4時：

            若設(shè)過橋速度最快的那個人過橋時間為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的大小即可知道那種方法更優(yōu) 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;
                
            }


            

            說句題外話，據(jù)說去年南大保研的面試題就是這道題，一模一樣，呵呵 只可惜我還沒到保研的時間。。。
		
            
			posted on 2009-03-28 22:58 abilitytao 閱讀(3108) 評論(10)  編輯 收藏 引用  
		
            
	
            
	
	





            
	    
    


            

            評論
            
	
	
			
            
				# re: POJ 1700-過河問題 經(jīng)典智力題
					
						2009-03-29 01:03
					
				陳梓瀚(vczh)
			
            
			
            
				將每一種分布式為節(jié)點(diǎn)，節(jié)點(diǎn)之間的邊權(quán)重是時間，作用是人的轉(zhuǎn)移。然后求最短路徑。  回復(fù)  更多評論
				  
			
            
		
			
            
				# re: POJ 1700-過河問題 經(jīng)典智力題[未登錄]
					
						2009-03-29 13:44
					
				abilitytao
			
            
			
            
				@陳梓瀚(vczh)

            能否說得再具體一些呢？

            雖然最短路算法Dij和floyd我也比較熟 但是我覺得這樣做貌似有些困難  回復(fù)  更多評論
				  
			
            
		
			
            
				# re: POJ 1700-過河問題 經(jīng)典智力題
					
						2009-03-29 14:58
					
				funcoding
			
            
			
            
				多謝LZ分享...

            LZ代碼一點(diǎn)注釋都沒的,還好這個比較短...

            但是時間久了,還是會忘了某些變量的含義...

            希望能養(yǎng)成習(xí)慣...  回復(fù)  更多評論
				  
			
            
		
			
            
				# re: POJ 1700-過河問題 經(jīng)典智力題[未登錄]
					
						2009-03-29 15:05
					
				abilitytao
			
            
			
            
				@funcoding

            我已經(jīng)把思路寫得很清楚了丫 :-)

              回復(fù)  更多評論
				  
			
            
		
			
            
				# re: POJ 1700-過河問題 經(jīng)典智力題[未登錄]
					
						2009-03-29 15:30
					
				abilitytao
			
            
			
            
				@funcoding

            不過還是要謝謝您的提醒 以后我會注意一下

              回復(fù)  更多評論
				  
			
            
		
			
            
				# re: POJ 1700-過河問題 經(jīng)典智力題[未登錄]
					
						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 了呢？


              回復(fù)  更多評論
				  
			
            
		
			
            
				# re: POJ 1700-過河問題 經(jīng)典智力題[未登錄]
					
						2009-04-04 15:32
					
				菜鳥
			
            
			
            
				就是好象最后b還沒有過去，就結(jié)束過河了……  回復(fù)  更多評論
				  
			
            
		
			
            
				# re: POJ 1700-過河問題 經(jīng)典智力題[未登錄]
					
						2009-04-04 16:42
					
				菜鳥
			
            
			
            
				知道了…………
            還是謝謝你……

              回復(fù)  更多評論
				  
			
            
		
			
            
				# re: POJ 1700-過河問題 經(jīng)典智力題
					
						2009-04-04 17:05
					
				abilitytao
			
            
			
            
				@菜鳥

            你沒看懂我的意思 其實(shí)以上的分析給出的是每一步的決策

            是一個循環(huán)，你沒有注意到while(n)這個循環(huán)語句嗎？

            當(dāng)剩下的人數(shù)不斷變化的時候，我們要根據(jù)人數(shù)的情況做相應(yīng)的決策。

            并不是一次就全都過去了丫:-)  回復(fù)  更多評論
				  
			
            
		
			
            
				# re: POJ 1700-過河問題 經(jīng)典智力題
					
						2009-07-31 12:41
					
				Linz
			
            
			
            
				分析得很透徹。贊  回復(fù)  更多評論
				  
			
            
		

            




            



            


            

	
            
		
		
            只有注冊用戶登錄后才能發(fā)表評論。
            
		
            
		
				
		
		
		
            
		
            			
		
		
		
		
            
		
            
			
		
            
		
            
			
		
            
		
            
			
            網(wǎng)站導(dǎo)航:
			博客園  
			IT新聞  
			BlogJava  			
			博問  
			Chat2DB  
			管理
			
            		
		
            
		
            
			
				

            


            

            		
		
            
	
            	

            



            

				

            


    
    







            
	   
	



日本久久久久久中文字幕|
中文字幕无码免费久久|
久久美女人爽女人爽|
色综合久久中文综合网|
久久久精品久久久久久|
久久婷婷色综合一区二区|
久久国产色AV免费看|
久久AAAA片一区二区|
久久综合九色综合网站|
青青青青久久精品国产h|
一本久久a久久精品综合香蕉|
狠狠色丁香久久婷婷综合|
国产精品久久网|
亚洲愉拍99热成人精品热久久|
久久精品国产影库免费看|
亚洲精品美女久久久久99小说|
www性久久久com|
久久久国产视频|
国产成人精品综合久久久|
欧美一区二区三区久久综|
久久久久这里只有精品
|
久久久久人妻一区二区三区vr|
品成人欧美大片久久国产欧美|
亚洲国产精品久久电影欧美|
精品久久综合1区2区3区激情|
久久精品无码专区免费青青|
久久精品国产99久久久古代|
久久久久久无码国产精品中文字幕|
久久久久无码精品国产不卡|
狠狠色婷婷久久综合频道日韩
|
久久精品国产亚洲5555|
久久精品国产精品亚洲毛片|
狠狠色丁香久久婷婷综合|
亚洲另类欧美综合久久图片区|
久久久国产精华液|
久久免费国产精品|
韩国三级中文字幕hd久久精品|
9999国产精品欧美久久久久久|
国产精品福利一区二区久久|
99久久er这里只有精品18|
A狠狠久久蜜臀婷色中文网|