题目：uva714 - Copying Books(最大值最小化）

题目大意：给出n本书，每本书的值代表这本书的页数。然后给定m个scribers，每个scriber至少要抄一本书，或者连续的几本书。每个scriber的工作量就等于他要抄的书的页数之和。问怎样划分能使的scribers中工作量的最大值最小。这里要求答案如果有多种的话就输出前面的和比较小的那个划分。

解题思路：最大值最小化问题。

二分尝试可能的最大值，然后如果在这个最大值的情况下可以划分的话，说明最大值可能是这个值，也可能更小。如果不能划分的话说明这个最大值不够大。

划分的时候从后面往前面划分，保证后面的比较大。

代码：

#include 
  
   
#include 
   
     const int N = 505; typedef long long ll; int n, m; ll max_num, min_num; int books[N]; int visit[N]; ll Min (const ll a, const ll b) { return a < b ? a : b; } int divide (ll value) { int i = n - 1; int count = 0; ll sum; while (i >= 0) { sum = 0; if (sum + books[i] > value) return m + 1; while (i >= 0 && sum + books[i] <= value) { sum += books[i--]; } if (i >= 0) visit[i] = 1; count++; } return count; } int bsearch () { ll left = min_num; ll right = max_num; ll mid; while (left < right) { mid = left + ((right - left)>>1); if (divide (mid) <= m) right = mid; else left = mid + 1; } return right; } void solve () { ll ans = bsearch(); memset (visit, 0, sizeof (visit)); int cnt = divide (ans); for (int i = 0; i < n - 1 && cnt < m; i++) { if (!visit[i]) { visit[i] = 1; cnt++; } } } int main () { int t; scanf ("%d", &t); while (t--) { max_num = 0; scanf ("%d%d", &n, &m); for (int i = 0; i < n; i++) { scanf ("%d", &books[i]); max_num += books[i]; if (i == 0) min_num = books[i]; else min_num = Min(min_num, books[i]); } memset (visit, 0, sizeof (visit)); if (m != 1) solve(); for (int i = 0; i < n - 1; i++) { printf ("%d ", books[i]); if (visit[i]) printf ("/ "); } printf ("%d\n", books[n - 1]); } return 0; }