題目：http://poj.org/problem?id=3273

? ? 當(dāng)分成的組數(shù)越多，所有組的最大值就會越小或不變，這一點(diǎn)不難證明：
? ? 如果當(dāng)前分成了group組，最大值是max，那么max的這一組天數(shù)>=1，這時(shí)把max的這一組再分成2組，總的組數(shù)變成了group+1,最大值顯然會減小或不變（當(dāng)還有另一組是max或者max組只包含一天時(shí)不變）。
? ? 所以組數(shù)和本題的答案是單調(diào)的關(guān)系。
? ? 設(shè)答案在區(qū)間[low, high]，不難看出low是花費(fèi)最多的一天的值，high是每天花費(fèi)的總和。這樣二分尋找答案，效率肯定是很高的。本題確實(shí)比較難理解，看了一個(gè)小時(shí)才差不多理解了，更多二分的細(xì)節(jié)在代碼注釋中。

　　

1 #include <stdio.h> 2 #include <string.h> 3 4 int n, m; //把n天分成m組 5 int money[100000]; //每天的錢數(shù) 6 7 //假設(shè)答案是mid，驗(yàn)證是否正確 8 //為了便于說明，設(shè)正確答案為ans 9 bool judge(int mid) 10 { 11 //sum表示一組的花費(fèi)，cnt表示分的組數(shù) 12 int sum = 0, cnt = 1; 13 for(int i = 0; i < n; i++) 14 { 15 //因?yàn)榧僭O(shè)答案是mid，所以當(dāng)sum + money[i] <= mid時(shí)，第i天可以分到上一組中。 16 //這一點(diǎn)很顯然，剩下的天數(shù)少了，ans當(dāng)然會更優(yōu) 17 if(sum + money[i] <= mid) 18 sum += money[i]; 19 20 //如果第i天不能分到上一組，那么只能再分下一組了，這時(shí)組數(shù)+1 21 else 22 { 23 sum = money[i]; 24 cnt++; 25 } 26 } 27 //如果分的組數(shù)>m，顯然這時(shí)假設(shè)的答案mid太小了，所以mid要增大 28 if(cnt > m) 29 return 0; 30 31 //否則cnt<=m。 32 //如果cnt<m，根據(jù)上面說的單調(diào)關(guān)系，分更多的組ans會更優(yōu)，即mid<ans 33 //如果cnt==m，說明此時(shí)可以在分m組的情況下ans<=mid，這時(shí)繼續(xù)嘗試在[low,mid]尋找ans 34 else 35 return 1; 36 } 37 38 int main() 39 { 40 int low = 0, high = 0; 41 scanf("%d %d", &n, &m); 42 for(int i = 0; i < n; i++) 43 { 44 //輸入每天的花費(fèi)，計(jì)算low和high 45 scanf("%d", &money[i]); 46 if(low < money[i]) 47 low = money[i]; 48 high += money[i]; 49 } 50 51 //二分尋找答案，循環(huán)在low==high時(shí)結(jié)束，這時(shí)low和high的值都是答案，輸出其中一個(gè)就可以 52 while(low < high) 53 { 54 //設(shè)答案是mid 55 int mid = (high + low) / 2; 56 if(judge(mid)) 57 high = mid;/*這里有一點(diǎn)不理解，為什么網(wǎng)上大多數(shù)代碼寫的high=mid-1也是正確的， 58 如果是在judge中提到的cnt==m的情況，那么ans是<=mid的啊，為什么ans所 59 在的區(qū)間可以跳過mid這個(gè)點(diǎn)呢？請知道的回復(fù)我，謝謝。*/ 60 else 61 low = mid + 1; 62 } 63 //輸出high也可以 64 printf("%d\n", low); 65 return 0; 66 } View Code

?

轉(zhuǎn)載于:https://www.cnblogs.com/wolfred7464/p/3370976.html

總結(jié)

以上是生活随笔為你收集整理的补充一下我对 POJ 3273 的理解，这肯定是我一生写的最多的题解。。。的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。