【藍橋杯學習記錄】分巧克力
一、題目
兒童節(jié)那天有K位小朋友到小明家做客。小明拿出了珍藏的巧克力招待小朋友們。小明一共有N塊巧克力，其中第i塊是 Hi ×Wi 的方格組成的長方形。為了公平起見，小明需要從這 N 塊巧克力中切出 K 塊巧克力分給小朋友們。切出的巧克力需要滿足：
1.形狀是正方形，邊長是整數(shù);
2.大小相同;
例如一塊 6x5 的巧克力可以切出 6 塊 2x2 的巧克力或者 2 塊 3x3 的巧克力。當然小朋友們都希望得到的巧克力盡可能大，你能幫小明計算出最大的邊長是多少么？
第一行包含兩個整數(shù)N,K
以下 N 行每行包含兩個整數(shù) H_i,W_i
輸出切出的正方形巧克力最大可能的邊長。
二、解題思路
循環(huán)邊長，開始采用的是邊長從2到100000，但是會超時，所以用二分查找。
畫圖可知（如圖一），每一塊巧克力的長和寬除以邊長再乘起來就是這塊巧克力再這個邊長下可以分出來的塊數(shù)，
所以再循環(huán)每個巧克力，將分出來的塊數(shù)相加，如果大于K（小孩子的人數(shù)），那么就可以，設置一個imax接收這個值，然后再去找更大的值，即讓first=mid+1，直到找到最大。否則tail=mid-1，去看看小的數(shù)里面有沒有滿足條件的
三、完整代碼
四、出現(xiàn)問題
出現(xiàn)的問題就是開始沒想到二分查找，還有就是二分查找的時候將tail=mid-1寫的tail=mid，導致循環(huán)無法退出，還有一個問題是開始想讓tail=每個巧克力長和寬中的最大值，但是我把tail=max（H[i],W[i])寫到了接收巧克力長和寬的循環(huán)里，這樣肯定是不對的，tial應該再和tail的值再作比較。
標簽：
