• <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水分,求最少需要多少時間。
            題解:第一時間就想到使用二分枚據答案+驗證這種思路,不過這題還是有些陷阱需要注意。
            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)  編輯 收藏 引用 所屬分類: 算法題解
            亚洲精品乱码久久久久久蜜桃不卡| 久久久一本精品99久久精品66| 久久国产福利免费| 久久精品中文字幕一区| 精品久久久久久久中文字幕| 色诱久久av| 久久国产精品无码一区二区三区 | 久久久久久久91精品免费观看| 7777精品久久久大香线蕉| 久久99国产精品一区二区| 久久影视国产亚洲| 成人久久精品一区二区三区| 欧美精品丝袜久久久中文字幕 | 99久久精品国内| 久久免费视频6| 久久综合狠狠综合久久| 国产福利电影一区二区三区久久久久成人精品综合 | 亚洲国产精品综合久久一线| 天天躁日日躁狠狠久久| 色婷婷综合久久久久中文字幕| 97热久久免费频精品99| 久久久无码精品亚洲日韩蜜臀浪潮| 99久久精品毛片免费播放| 97久久婷婷五月综合色d啪蜜芽| 久久综合中文字幕| 久久国产精品99国产精| 午夜精品久久影院蜜桃| 久久99精品国产麻豆蜜芽| 国产精品久久久久影视不卡| 伊人久久大香线蕉av一区| 久久91这里精品国产2020| 久久青草国产精品一区| 久久精品中文闷骚内射| 99久久国产精品免费一区二区| 色偷偷91久久综合噜噜噜噜| 久久免费大片| 久久久久人妻一区精品| 品成人欧美大片久久国产欧美...| 精品久久久久久国产| 一级做a爰片久久毛片人呢| 久久99国产精品久久99|