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

            PouringWater (SRM 439 Div2 500)

            題目鏈接:http://www.topcoder.com/stat?c=problem_statement&pm=10408&rd=13747

            最終的水要放在K個瓶子里面,而每個瓶子中的水的數量必須為2的整數冪,即最終的水數量n'要能分解成
            k個2的整數冪,也就是new_n的二進制表示中1的個數要<=k.

            用count(n)表示n的二進制表示中1的個數,如果count(n)<=k,那就不需要買瓶子了。
            如果count(n)>k,說明我們要找到第一個n'使得n'>n并且count(n')<=k。那就是說我們要減少n中1的個數。
            我們把n表示為x0ab.其中a為全1,b為全0. a,b的長度>=0.
            很明顯,第一個減少1的個數的n'應該為x1{(a+b)個0},也就是把ab全部變成0.ab前的0變為1.即加上一個1<<length(b).
            因為對b來說,無論增加多少都會增加1的個數。
            然后再判斷n'的1的個數,直到count(n)<=k。
            因為n最大為10^7,n'最大為10^8,int類型不會溢出。因此邊界條件就無需判斷了。

             1 #include <vector>
             2 #include <algorithm>
             3 #include <sstream>
             4 #include <string>
             5 #include <iostream>
             6 
             7 using namespace std;
             8 
             9 int count(int i)
            10 {
            11     int res = 0;
            12     while(i!=0){
            13         i&=(i-1);
            14         res++;
            15     }
            16 
            17     return res;
            18 }
            19 
            20          class PouringWater
            21               { 
            22               public
            23               int getMinBottles(int N, int K) 
            24                   { 
            25                       int res = 0;
            26                       int mask = 1;
            27 
            28                       while(count(N)>K){

            29                            //找到第一個1...第n次犯了沒把N&mask括號括起來的錯誤了。。。&的優先級<等號...
            30                           while( (N&mask)==0) mask<<=1;

            31                           //加上mask使得1的數目減少
            32                           N+=mask;
            33                           res += mask; 
            34                       }
            35 
            36                       return res;
            37                   } 
            38              
            39 




            posted on 2009-06-03 20:31 YZY 閱讀(284) 評論(0)  編輯 收藏 引用 所屬分類: AlgorithmTopCoder

            導航

            <2009年6月>
            31123456
            78910111213
            14151617181920
            21222324252627
            2829301234
            567891011

            統計

            常用鏈接

            留言簿(2)

            隨筆分類

            隨筆檔案

            搜索

            積分與排名

            最新評論

            閱讀排行榜

            久久久久亚洲AV片无码下载蜜桃| 国产午夜精品理论片久久影视| 国内精品久久久久久中文字幕| 午夜不卡888久久| 亚洲国产精品嫩草影院久久| 久久人妻少妇嫩草AV蜜桃| 久久香蕉国产线看观看乱码| 亚洲国产婷婷香蕉久久久久久| 色婷婷久久综合中文久久蜜桃av | 国产精品热久久无码av| 一本色综合久久| 久久免费精品一区二区| 97香蕉久久夜色精品国产| 久久久久久久尹人综合网亚洲| 久久久精品久久久久久 | 国产精品伦理久久久久久| 久久91精品国产91| 久久精品国产黑森林| 国产Av激情久久无码天堂| 久久亚洲sm情趣捆绑调教| 久久亚洲AV无码西西人体| 精品久久久久久无码专区不卡| 欧美日韩精品久久久久| 精品99久久aaa一级毛片| 国产精品美女久久久久网| 日韩精品久久久肉伦网站| 欧美精品乱码99久久蜜桃| 久久精品国产精品亚洲下载| 国产一区二区精品久久凹凸| 99久久免费国产精品热| 1000部精品久久久久久久久| 亚洲va久久久噜噜噜久久男同| 亚洲国产视频久久| 久久夜色精品国产噜噜亚洲a | 色综合久久中文字幕无码 | 国产精品久久国产精麻豆99网站| 久久精品国产99国产精品导航| 亚洲国产成人久久综合野外 | 国内精品九九久久久精品| 久久久久AV综合网成人 | 久久亚洲高清综合|