二分答案 POJ3273

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <queue>
 4 #include <cstring>
 5 #include <algorithm>
 6 
 7 using namespace std;
 8 
 9 int n,m;
10 int arr[100010];
11 int reans;
12 int flag;
13 
14 void dfs(int mi,int ma)
15 {
16     if(flag==1)
17         return ;
18     if(mi==ma)
19     {
20         flag=1;
21         reans=mi;
22         return ;
23     }
24     int num=1;
25     int tmp=0;
26     int ans=(mi+ma)/2;
27     for(int i=0;i<n;i++)
28     {
29         if(tmp+arr[i]<=ans)
30         {
31             tmp=tmp+arr[i];
32         }
33         else
34         {
35             tmp=arr[i];
36             num++;
37         }
38     }
39     if(num>m)
40     {
41         dfs(ans+1,ma);
42     }
43     else if(num<=m)
44     {
45         dfs(mi,ans);
46     }
47 }
48 
49 int main()
50 {
51     while(scanf("%d%d",&n,&m)!=EOF)
52     {
53         int ma=0;
54         for(int i=0;i<n;i++)
55         {
56             scanf("%d",&arr[i]);
57             if(arr[i]>ma)
58                 ma=arr[i];
59         }
60         flag=0;
61         dfs(ma,1000000000);
62         cout<<reans<<endl;
63     }
64     return 0;
65 }