首页 > 代码库 > poj 3273 Monthly Expence 简单二分

poj 3273 Monthly Expence 简单二分

 1 /**
 2 大意: 有连续的n天,每一天有一定的花费,将其分成m份,每一份占一天或者连续的几天,求这m份中的最大值
 3 思路:  二分其最大上限,看在此最大上线,能分成多少份,若大于m份,说明上限过小,需要扩大上限
 4           若小于m份,则说明,下限过大,需要缩小上限。
 5 **/
 6 #include <iostream>
 7 
 8 using namespace std;
 9 int c[100010]; // 记录,每天的花费 
10 int main()
11 {
12     int n,m;
13     cin>>n>>m;
14     int maxn =0,sum =0;
15     for(int i=1;i<=n;i++){
16         cin>>c[i];
17         if(c[i]>maxn) maxn = c[i];
18         sum += c[i];
19     }
20 
21     int mid ,low = maxn,high= sum;
22     while(high>low){
23         mid = (high + low )/2;
24         int cnt = 1,w =0;
25         for(int i=1;i<=n;i++){
26             w += c[i];
27             if(w>mid){
28                 cnt++;
29                 w = c[i];
30             }
31         }
32         if(cnt>m) low = mid +1;
33         else  high = mid -1;
34     }
35     cout<<low<<endl;
36     return 0;
37 }