题目传送门
1 /* 2题意：分成m个集合，使最大的集合值(求和)最小 3二分搜索：二分集合大小，判断能否有m个集合。 4 */ 5 #include <cstdio> 6 #include <algorithm> 7 #include <cstring> 8 #include <cmath> 9 using namespace std;10 11 const int MAXN = 1e5 + 10;12 const int INF = 0x3f3f3f3f;13 int a[MAXN];14 int n, m;15 16 bool check(int tot) {17int j = 1, sum = 0;18for (int i=1; i<=m; ++i) {19 sum = 0;20 while (j <= n && sum + a[j] <= tot) {21 sum += a[j++];22 }23 if (j == n + 1) return true;24}25return false;26 }27 28 int main(void) { //POJ 3273 Monthly Expense29//freopen ("POJ_3273.in", "r", stdin);30 31while (scanf ("%d%d", &n, &m) == 2) {32 int l = 0, r = 0;33 for (int i=1; i<=n; ++i) {34 scanf ("%d", &a[i]);35 if (l < a[i]) l = a[i];36 r += a[i];37 }38 39 while (l < r) {40 int mid = (l + r) >> 1;41 if (check (mid)) r = mid;42 else l = mid + 1;43 }44 printf ("%d\n", l);45}46 47return 0;48 }
