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

    
            

            




            







												


        
			
			


			
            
				
					
	
            
		
            
			pku 1771 Elevator Stopping Plan 二分+貪心判斷可行性
		
            
		題意是這樣的：
            一幢大樓有21層，只有一個(gè)電梯，電梯上一層樓需要4秒。停一次需要10秒，人爬一層樓需要20秒，現(xiàn)有一些人想通過(guò)電梯上樓，電梯選擇性的停一些樓層，使得最后一個(gè)人到達(dá)目的樓層的時(shí)間最小。
            像這種最大最小問(wèn)題一般思路就是二分+驗(yàn)證可行性。這道題驗(yàn)證可行性可采用貪心方法，即電梯停靠的越上層越好，每次停靠的樓層用不等式t-10*num-4*(i-1)-20*(j-i)=0.解出。具體看代碼吧- -
            這題做的時(shí)候有點(diǎn)NC，竟然忘了排序。。汗。。
            

             1# include <iostream>
             2# include <vector>
             3# include <algorithm>
             4# define abs(a) ((a)>0?(a):-(a))
             5using namespace std;
             6int data[50],n;
             7void make(int limit)
             8{
             9    int used=0,p=0,last=1;
            10    vector<int> ans;
            11    while(p<n&&10*used+(last-1)*4+abs(data[p]-last)*20<=limit)
            12          p++; 
            13    while(p<n)
            14    {
            15
            16       int up=(limit+20*data[p]+4-10*used)/24;
            17       last=up;
            18       ans.push_back(last);
            19       p++;
            20       while(p<n&&10*used+(last-1)*4+abs(data[p]-last)*20<=limit)
            21          p++; 
            22       used++;
            23    }
            24    cout<<ans.size();
            25    for(int i=0;i<ans.size();i++)
            26      cout<<" "<<ans[i];
            27    cout<<endl;
            28}
            29bool chk(int limit)
            30{
            31    int used=0,p=0,last=1;
            32    while(p<n&&10*used+(last-1)*4+abs(data[p]-last)*20<=limit)
            33          p++;
            34    while(p<n)
            35    {
            36
            37       if(10*used+(data[p]-1)*4>limit) return false; 
            38       int up=(limit+20*data[p]+4-10*used)/24;
            39       //if(up>31) up=31;    
            40       last=up;
            41       p++;
            42       while(p<n&&10*used+(last-1)*4+abs(data[p]-last)*20<=limit)
            43          p++;
            44       used++;
            45        
            46    }
            47    return true;
            48}
            49int main()
            50{
            51    while(true)
            52    {
            53        int s=0,e=-1;
            54        cin>>n;
            55        if(!n) break;
            56        for(int i=0;i<n;i++)
            57        {
            58             cin>>data[i];
            59             e=((data[i]-1)*20>e?(data[i]-1)*20:e);
            60        }
            61        sort(data,data+n);
            62      //  int *p=unique(data,data+n);
            63       // n=p-data;
            64        while(s<=e)
            65        {
            66           int mid=(s+e)>>1;
            67           if(chk(mid))
            68              e=mid-1;
            69           else
            70              s=mid+1;
            71        }
            72        cout<<s<<endl;
            73        make(s);
            74    }
            75    return 0;
            76}
            77
            78
            

		
            
			posted on 2010-10-19 14:24 yzhw 閱讀(222) 評(píng)論(0)  編輯 收藏 引用  所屬分類: search 、others 
		
            
	
            
	
	


	


            
	    
    




            






            

				
				

			
            
			
            
				
					
            
	
            
		
            <2010年10月>
            
	
            日一二三四五六
            262728293012
            3456789
            10111213141516
            17181920212223
            24252627282930
            31123456
            

            

					

            導(dǎo)航
            

					

            統(tǒng)計(jì)
            
	
					

            公告
            
	
            統(tǒng)計(jì)系統(tǒng)
            

					

            留言簿(1)
            


		
            隨筆分類(227)
            
		
				
			
	
		
            文章分類(2)
            
		
				
			
	
		
            OJ
            
		
				
			
	


            最新隨筆
            




            搜索
            



            積分與排名
            



            最新評(píng)論
	
            

            
	
			
		

            


            閱讀排行榜
            


				
			
            
			
			
			
			
			 

	
    
    







            
	   
	



久久精品日日躁夜夜躁欧美|
人妻无码久久一区二区三区免费|
成人精品一区二区久久久|
久久国产免费|
久久精品国产亚洲77777|
国内精品久久久久国产盗摄|
狠狠色噜噜色狠狠狠综合久久|
www.久久热.com|
久久精品免费一区二区|
青青国产成人久久91网|
国内精品久久久久影院老司|
久久综合久久综合久久综合|
色狠狠久久综合网|
国产2021久久精品|
国产精品久久一区二区三区|
三级三级久久三级久久|
国产一区二区精品久久岳|
久久精品国产亚洲AV无码偷窥|
久久精品无码免费不卡|
亚洲国产成人久久精品动漫|
亚洲国产精品无码久久久蜜芽|
久久久久久午夜精品|
久久人人爽人人爽人人片AV东京热|
久久国产色AV免费看|
色老头网站久久网|
中文精品99久久国产
|
伊人久久大香线蕉亚洲五月天|
国产亚洲美女精品久久久|
亚洲国产精品人久久|
久久精品国产秦先生|
国产人久久人人人人爽|
精品少妇人妻av无码久久|
国产成人久久精品一区二区三区|
伊人久久大香线焦AV综合影院|
久久精品国产亚洲AV香蕉|
麻豆久久久9性大片|
中文字幕久久精品无码|
日韩精品久久无码中文字幕|
久久综合给久久狠狠97色|
欧美黑人又粗又大久久久|
久久成人国产精品|