• <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層，只有一個電梯，電梯上一層樓需要4秒。停一次需要10秒，人爬一層樓需要20秒，現(xiàn)有一些人想通過電梯上樓，電梯選擇性的停一些樓層，使得最后一個人到達目的樓層的時間最小。
            像這種最大最小問題一般思路就是二分+驗證可行性。這道題驗證可行性可采用貪心方法，即電梯停靠的越上層越好，每次停靠的樓層用不等式t-10*num-4*(i-1)-20*(j-i)=0.解出。具體看代碼吧- -
            這題做的時候有點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 閱讀(216) 評論(0)  編輯 收藏 引用  所屬分類: search 、others 
		
            
	
            
	
	


	


            
	    
    




            






            

				
				

			
            
			
            
				
					
            
	
            
		
            <2010年12月>
            
	
            日一二三四五六
            2829301234
            567891011
            12131415161718
            19202122232425
            2627282930311
            2345678
            

            

					

            導航
            

					

            統(tǒng)計
            
	
					

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

					

            留言簿(1)
            


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


            最新隨筆
            




            搜索
            



            積分與排名
            



            最新評論
	
            

            
	
			
		

            


            閱讀排行榜
            


				
			
            
			
			
			
			
			 

	
    
    







            
	   
	



久久久久久亚洲精品成人|
青青热久久国产久精品
|
婷婷久久香蕉五月综合加勒比|
波多野结衣久久一区二区|
午夜精品久久久久久久久|
狠色狠色狠狠色综合久久|
久久精品a亚洲国产v高清不卡|
欧美午夜精品久久久久免费视|
青青青国产成人久久111网站|
亚洲国产精品综合久久网络|
久久精品亚洲中文字幕无码麻豆|
国产三级精品久久|
色偷偷偷久久伊人大杳蕉|
久久国产午夜精品一区二区三区|
久久天天躁狠狠躁夜夜躁2014|
国产毛片久久久久久国产毛片|
亚洲人成网站999久久久综合|
久久久久亚洲AV成人片|
亚洲国产香蕉人人爽成AV片久久|
国产成人无码久久久精品一|
精品久久久久成人码免费动漫|
国产精品久久久久影视不卡|
久久精品中文字幕一区|
精品久久人人做人人爽综合
|
久久久精品人妻一区二区三区四|
色综合久久中文色婷婷|
99久久精品影院老鸭窝|
久久综合久久自在自线精品自|
天天影视色香欲综合久久|
国产精品美女久久久久AV福利|
久久精品国产清高在天天线|
亚洲国产精品久久电影欧美|
久久成人小视频|
久久久国产亚洲精品|
久久综合成人网|
亚洲中文字幕无码一久久区|
欧美激情精品久久久久久久|
国产精品成人久久久久三级午夜电影|
aaa级精品久久久国产片|
久久香蕉国产线看观看乱码|
国产精品久久久久久久久免费|