ACM投票——二分法

ACM投票——二分法

問題描述
有N個城市，每個城市有Ai個人。
現在要開始投票，每個人有一張票。
作為領導者，你有B個箱子，你必須要將這B個箱子分發到N個城市去，每個城市至少需要一個箱子。
每個人都必須要投票，不能棄票，也就是說要把票丟進箱子裡去(每個城市有Ai張票)。
現在問你，怎麼分配這B個箱子才能使這些所有箱子裡中票數最大的那個箱子裡的票最少?

輸入
輸入包含一個數N(1<=N<=500,000)和B(N<=B<=2,000,000)。
接下來N行包含N個數，每個數Ai(1<=Ai<=5,000,000)表示每個城市的人數。
輸入N為-1，B為-1時結束。

輸出
輸出那個帶兵量最多的將領所帶的士兵數。

樣例輸入
2 7
200000
500000
4 6
120
2680
3400
200
-1 -1

樣例輸出
100000
1700

 

分析

若每個城市都先分得一個箱子，那麼目前的答案就是max(Ai(1<=i<=n))。所以，我們必須要給最大值的那個城市還需要至少分配一個箱子，那麼答案肯定不再是那個城市(也有可能有某個城市的人數跟該城市人數一樣，那麼答案還是沒變)。
接下來如果你還有箱子，你肯定要給次大值的那個城市至少再分配一個箱子；
接下來如果你還有箱子，你肯定要給次次大值的那個城市至少再分配一個箱子；
接下來如果你還有箱子，你肯定要給次次次大值的那個城市至少再分配一個箱子；
接下來如果你還有箱子，你肯定要給次次次次大值的那個城市至少再分配一個箱子；
。。。
直到什麼時候呢？
直到原先那個最大值城市的票數的一半(奇數需要再加1)大於等於了你剛剛從大到小排列的城市的那個票數，為什麼？
因為那個城市的後面的票數肯定小於等於那個城市，那麼這些城市中沒有一個票數是比那個最大值城市的票數的一半還要大，也就是說當前狀態下，所有城市中，原先那個最大值城市的票數的一半成了當前最大值。

解題：你想到了什麼？——二分！
我們二分票數，票數范圍是1到某個城市的最大票數。
記l=1, r=max,那麼mid=(1+max)/2;
假設mid就是答案，那麼我們需要統計一下一共需要幾個箱子。
 

int num = 0;

for (int i = 1; i <= n; i++)

{

    if (a[i] % mid) num += a[i] / mid + 1;

    else num += a[i] / mid;

}

那麼最後需要num個箱子，但是我們有B個箱子，所以需要比較一下。
如果num>B，說明我們需要的箱子不夠，也就是說票數不小於mid值的那些城市中有些城市分不到足夠的箱子，所以，我們的最終答案肯定是大於num的。那麼二分范圍落在[mid + 1, max]。
如果num<=B，說明我們需要的箱子很夠，也就是說票數不小於mid值的那些城市中所有城市都能分到足夠的箱子，所以，我們的最終答案肯定是小於等於num的。那麼二分范圍落在[1, mid]。
然後繼續二分，直到最終的范圍l>=r為止結束。