Monthly Expense(二分)

题意：将n个数分成连续的m组，使得这些组里的数的最大的和最小，输出这个组的和。

思路：根据上下界二分逼近。。

 1 #include <stdio.h>
 2 #include <math.h>
 3 #include <algorithm>
 4 using namespace std;
 5 
 6 int main()
 7 {
 8     int cost[100010];
 9     int n,m,high = 0,low = 0;
10     scanf("%d %d",&n,&m);
11     for (int i = 0; i < n; i++)
12     {
13         scanf("%d",&cost[i]);
14         high+=cost[i];//上界
15         low = max(low,cost[i]);//下界
16     }
17     int i,mid;
18     while(low <= high)
19     {
20         int cnt = 0,sum = 0;
21         mid = (low+high)/2;
22         for (i = 0; i < n; i++)
23         {
24             sum+=cost[i];
25             if (sum > mid)
26             {
27                 cnt++;
28                 sum = cost[i];
29             }
30         }
31         cnt++;
32         if (cnt > m)//修改下界
33             low = mid+1;
34         else           
35             high = mid-1;//修改上界
36 
37     }
38     printf("%d
",mid);
39     return 0;
40 }

View Code