POJ 4135 月度开销

题目链接：http://bailian.openjudge.cn/practice/4135

题目解析：二分选择答案

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 int n, m;
 4 const int N = 100010;
 5 int a[N];
 6 bool valid(int mid) {
 7     int group = 1, rest = mid;
 8     for (int i = 1; i <= n; i++) {
 9         if (rest >= a[i]) {
10             rest -= a[i];
11         } else {
12             group++;
13             rest = mid - a[i];
14         }
15     }
16     return group <= m;
17 }
18 int main() {
19     cin >> n >> m;
20     int sum_of_ai = 0;
21     int maxx = 0;
22     for (int i = 1; i <= n; i++) {
23         cin >> a[i];
24         sum_of_ai += a[i];
25         maxx = max(maxx, a[i]);
26     }
27     int l = maxx, r = sum_of_ai;
28     while (l < r) {
29         int mid = (l + r) >> 1;
30         if (valid(mid)) {
31             r = mid;
32         } else {
33             l = mid + 1;
34         }
35     }
36     cout << l << endl;
37     return 0;
38 }