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

    
            

            




            







												


        




            
	
		
            
			


            
posts - 33, 
comments - 33, 
trackbacks - 0


            
	

            


            
	
					


            
	
	題意：烘干機，給出一堆衣服的水分a[i]，在不加烘干機情況下自動每一分鐘減少1水分，每分鐘可以變改衣服(i)到烘干機中，每分鐘減少k水分，求最少需要多少時間。
            題解：第一時間就想到使用二分枚據(jù)答案+驗證這種思路，不過這題還是有些陷阱需要注意。
            1. 驗證答案時，如果 a[i] <= mid，讓它自然烘干即可 ； 如果a[i] > mid，那么烘干這件衣服可以分成兩段時間：使用烘干機時間x1 + 自然烘干時間x2，那么可以列出等式：mid = x1 + x2; a[i] <= kx1+x2；于是得x1 >= (a[i] -mid)/(k-1);即得使用烘干機的最少時間x1
            2.注意當k==1時，k-1 == 0，需要特殊處理，直接打出ans = maxV
            3.注意當求left+right時，結果可能超出范圍，正確的方法應該是left + (right - left)*0.5;

            #include <stdio.h>

            const int N = 100005;
            int n;
            int a[N];
            int k;

            bool check(int _value)
            {
                            int cnt = 0;
                            for (int i = 0; i < n; ++i)
                            {
                                if (a[i] > _value)
                                {
                                    double kk = ((double)(a[i] - _value))/(k-1);
                        cnt             += (int)kk;
                                    if (kk - (int)kk > 0)
                                    {
                                        ++cnt;
                        }
                                    if (cnt > _value)
                                    {
                                        return false;
                        }
                    }
                }

                            return (cnt <= _value);
            }

            int BinarySearch(int _low,int _high)
            {
                            int left = _low;
                            int right = _high;
                            int mid;
                            int ans = _high;
                            while(left <= right)
                            {
                    mid             = (left+(right-left)*0.5);
                                if (check(mid))
                                {
                        ans             = mid;
                        right             = mid - 1;
                    }
                                else
                                {
                        left             = mid + 1;
                    }
                }
                            return ans;
            }

            void Test()
            {
                            int maxV = 0;
                            for (int i = 0; i < n; ++i)
                            {
                    scanf(            "%d",&a[i]);
                                if (maxV < a[i])
                                {
                        maxV             = a[i];
                    }
                }
                scanf(            "%d",&k);
                            if (k == 1)
                            {
                    printf(            "%d\n",maxV);
                }
                            else
                    printf(            "%d\n",BinarySearch(0,maxV));
            }

            int main()
            {
                            while(scanf("%d",&n) != EOF)
                            {
                    Test();
                }
                            return 0;
            }


            
	
            posted on 2011-11-09 12:45 bennycen 閱讀(1521) 評論(1)  編輯 收藏 引用  所屬分類: 算法題解 
            

            







            
	    
    










            






            

				

            




    
    







            
	   
	



伊人久久精品线影院|
亚洲AV无码久久精品狠狠爱浪潮
|
国产午夜精品理论片久久影视|
狠狠色丁香久久婷婷综合蜜芽五月
|
久久久久久国产精品免费无码|
亚洲AV乱码久久精品蜜桃|
人妻无码αv中文字幕久久琪琪布|
国产一区二区三区久久|
久久亚洲精品无码观看不卡|
久久久久亚洲av综合波多野结衣|
久久99精品国产自在现线小黄鸭
|
一本久久a久久精品亚洲|
久久99热国产这有精品|
久久精品中文无码资源站|
成人亚洲欧美久久久久
|
久久久www免费人成精品|
新狼窝色AV性久久久久久|
久久国产成人精品国产成人亚洲|
国产精品久久久久久久|
亚洲一级Av无码毛片久久精品|
国产成人精品久久二区二区|
99久久婷婷国产综合精品草原|
久久久久波多野结衣高潮|
国产精品久久久久蜜芽|
亚洲精品美女久久久久99|
午夜视频久久久久一区|
精品综合久久久久久97超人|
一本色道久久99一综合|
97视频久久久|
精品国产VA久久久久久久冰|
久久综合狠狠综合久久综合88|
日产精品久久久久久久|
国产免费久久精品99久久|
午夜精品久久久久成人|
久久精品99无色码中文字幕|
色婷婷狠狠久久综合五月|
久久国产免费直播|
久久99热这里只有精品国产|
久久人人爽人人爽人人爽|
国产精品久久久久久久|
亚洲人AV永久一区二区三区久久|