Posted on 2008-09-01 00:15
Hero 閱讀(425)
評論(0) 編輯 收藏 引用 所屬分類:
代碼如詩－－ACM
1 //PKU 3273 Accepted 608K 94MS C++ 1044B Monthly Expense
2
3 //二分答案
4
5 #include <stdio.h>
6 #include <stdlib.h>
7 #include <string.h>
8 #include <math.h>
9
10 const int INF = 99999999 ;
11 const int size = 100100 ;
12
13 int data[size] ;
14 int insum ;
15 int inmax ;
16 int inn, inm ;
17
18 void input()
19 {
20 insum = 0 ; inmax = -1 ;
21 for( int i=1; i<=inn; i++ )
22 {
23 scanf( "%d", &data[i] ) ; insum += data[i] ;
24 inmax = inmax > data[i] ? inmax : data[i] ;
25 }
26 }
27
28 int test( int mid )
29 {
30 int cnt = 1 ; int tsum = 0 ;
31 for( int i=1; i<=inn; i++ )
32 {
33 if( tsum + data[i] > mid )
34 {
35 cnt++ ; tsum = data[i] ;
36 }
37 else
38 {
39 tsum += data[i] ;
40 }
41 }
42
43 return cnt ;
44 }
45
46 void process()
47 {
48 int left = inmax ; int right = insum ; int mid ;
49
50 while( left < right )
51 {
52 mid = ( (left+right)/2 ) ;
53
54 int cnt = test( mid ) ;
55 if( cnt > inm ) left = mid + 1 ;
56 else right = mid ;
57 }
58
59 printf( "%d\n", right ) ;
60 }
61
62 int main()
63 {
64 //freopen( "in.txt", "r", stdin ) ;
65
66 while( scanf( "%d %d", &inn, &inm ) != EOF )
67 {
68 input() ;
69
70 process() ;
71
72 //output() ;
73 }
74
75 return 0 ;
76 }