POJ 1505 Copying Books 二分 + 贪心
来源：http://poj.org/problem?id=1505
题意：给一些书，这些书有不同的页数，让把这些书分成k份，必须是连续的，问这些份中页数和的最大值最小是多少。
思路：首先可以用二分枚举出最大的最小值，然后输出的时候从后向前判断输出
代码：
#include <iostream>#include <string.h>#include <cstdio>#include <algorithm>#include <vector>using namespace std;typedef long long LL;const int N = 510;vector<int> vv[N];int num[N];LL min(LL a,LL b){return a < b ? a : b;}int main(){int numcase;scanf("%d",&numcase);while(numcase--){ int n,k; scanf("%d%d",&n,&k); memset(vv,0,sizeof(vv)); memset(num,0,sizeof(num)); LL sum = 0,maxvalue = 0; for(int i = 0; i < n; ++i){ scanf("%d",&num[i]); if(maxvalue < num[i]) maxvalue = num[i]; sum += num[i]; } LL lp = maxvalue,rp = sum; LL ans = 0; while(lp <= rp){ LL mid = (lp + rp) / 2; int cnt = 0; LL total = 0; for(int i = n-1; i >= 0; ){ if(total + num[i] > mid){ total = 0; cnt++; continue; } total += num[i]; if(i == 0 && total <= mid) cnt++; --i; } if(cnt <= k){ rp = mid - 1; ans = mid; } else if(cnt > k){ lp = mid + 1; } } int id = 0; LL ss = 0; LL valueans = 0; for(int i = k-1; i < n; ++i) valueans += num[i]; valueans = min(valueans,ans); for(int i = n-1; i >= 0; ){ if(ss + num[i] > valueans){ id++; ss = 0; valueans = 0; for(int j = k - 1 - id; j <= i; ++j){ valueans += num[j]; } valueans = min(valueans,ans); continue; } ss += num[i]; vv[id].push_back(num[i]); --i; } for(int i = id; i >= 0; --i){ if(i != id ) printf(" "); for(int j = vv[i].size() - 1; j >= 0; --j){ printf("%d ",vv[i][j]); } if(i != 0) printf("/"); } printf("\n");}return 0;}