Posted on 2008-05-20 09:58
superman 阅读(547)
评论(0) 编辑 收藏 引用 所属分类:
POJ
1 /* Accepted 816K 829MS G++ 899B */
2 #include <iostream>
3
4 using namespace std;
5
6 int main()
7 {
8 int n, m, x[100000];
9
10 cin >> n >> m;
11 for(int i = 0; i < n; i++)
12 cin >> x[i];
13
14 int sum = 0;
15 for(int i = 0; i < n; i++)
16 sum += x[i];
17
18 int l = 0, r = sum;
19 while(l + 1 < r)
20 {
21 int mid = (l + r) / 2;
22
23 int i, cnt = 0, left = mid;
24
25 for(i = 0; i < n && cnt < m; i++)
26 {
27 if(x[i] > mid)
28 break;
29 if(left - x[i] >= 0)
30 left -= x[i];
31 else
32 {
33 cnt++;
34 left = mid - x[i];
35 }
36 }
37
38 if(i == n)
39 r = mid;
40 else
41 l = mid;
42 }
43
44 cout << r << endl;
45
46 return 0;
47 }
48