題意：給一些書，這些書有不同的頁數，讓把這些書分成k份，必須是連續的，問這些份中頁數和的最大值最小是多少。

解題思路：知道了頁數和的范圍，而且書都是連續的，要找到頁數和最大值的最小值可以直接二分答案。。

AC:

#include<iostream> #include<cstdlib> #include<cstring> using namespace std;const int MAXM = 505; int m,k; int book[MAXM]; bool vis[MAXM];int divide(int x) {int sum=0,cnt=1;memset(vis,false,sizeof(vis));for(int i=m;i>=1;i--){sum+=book[i];if(sum>x){cnt++;sum=book[i];vis[i]=true;}}return cnt; }void print() {cout<<book[1];for(int i=2;i<=m;i++){if(vis[i-1]) cout<<" /";cout<<' '<<book[i];}cout<<endl; }int main() { int cas;cin>>cas;while(cas--){cin>>m>>k;int l=0,r=0,mid=0;;for(int i=1;i<=m;i++){cin>>book[i];r+=book[i];if(l<book[i]) l=book[i];}while(l<r) //二分搜索最大值中的最小值（參見劉汝佳《算法競賽入門經典》P151）{mid=(l+r)>>1;if(divide(mid)<=k) r=mid; //這里不能是r=mid-1，原因可參見《算法競賽入門經典》else l=mid+1;}int cnt=divide(r);for(int i=1;i<=m && cnt<k;i++) //可能分得不足k次，那么就把前面的每一本書分給一個人超(題目要求){if(!vis[i]){vis[i]=true;cnt++;}}print();}return 0; }

總結

以上是生活随笔為你收集整理的POJ 1505(二分+贪心)的全部內容，希望文章能夠幫你解決所遇到的問題。

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