tips：

　　1.用條件判斷左右區間該怎么更新

　　2.答案在區間范圍內是否是整數變化

　　3.這個區間變換還是沒有搞的太懂

　　4.二分超時的原因是二分的區間更新寫錯了

　　5.最大化最小值？？

//二分超時很大一部分原因是二分時陷入了死循環 //http://zhenzxie.iteye.com/blog/1446986 //https://www.cnblogs.com/helica/p/5173800.html #include<cstdio> using namespace std; const int MM=100010; int a[MM]; int n,m; int L,R; int summ; int judge(int x){int ans=1;int sum=0;for(int i=0;i<n;i++){if(sum+a[i]<=x){sum+=a[i];}else{ans++;sum=a[i];}}//ans=summ/x;return ans; } int main(){while(scanf("%d%d",&n,&m)!=EOF){int tmp=0;R=0;for(int i=0;i<n;i++){scanf("%d",&a[i]);if(a[i]>tmp){tmp=a[i];}R+=a[i];}L=tmp;summ=R;while(L<R){//等于的話不用判斷，確定了唯一的位置int mid=L+(R-L)/2;if(judge(mid)<=m){R=mid-1;}else{L=mid+1;}}printf("%d\n",L);}return 0; } View Code

?　　6.還可以不對 ==號進行處理---解決模糊問題？比如說5.

//二分超時很大一部分原因是二分時陷入了死循環 //http://zhenzxie.iteye.com/blog/1446986 //https://www.cnblogs.com/helica/p/5173800.html #include<cstdio> using namespace std; const int MM=100010; int a[MM]; int n,m; int L,R; int summ; int judge(int x){int ans=1;int sum=0;for(int i=0;i<n;i++){if(sum+a[i]<=x){sum+=a[i];}else{ans++;sum=a[i];}}//ans=summ/x;return ans; } int main(){while(scanf("%d%d",&n,&m)!=EOF){int tmp=0;R=0;for(int i=0;i<n;i++){scanf("%d",&a[i]);if(a[i]>tmp){tmp=a[i];}R+=a[i];}L=tmp;summ=R;while(L<R){//等于的話不用判斷，確定了唯一的位置int mid=L+(R-L)/2;if(judge(mid)<m){R=mid-1;}if(judge(mid)>m)L=mid+1;}}printf("%d\n",L);}return 0; } View Code

?

轉載于:https://www.cnblogs.com/SUMaywlx/p/9535456.html

總結

以上是生活随笔為你收集整理的poj3273---Monthly Expense的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。