二分搜索 POJ 3273 Monthly Expense-白红宇

二分搜索 POJ 3273 Monthly Expense

阅读量：5313 次

发布时间：2019-06-14

本文共 1185 字，大约阅读时间需要 3 分钟。

1 /* 2     题意：分成m个集合，使最大的集合值(求和)最小 3     二分搜索：二分集合大小，判断能否有m个集合。 4 */ 5 #include 
     
       6 #include 
      
        7 #include 
       
         8 #include 
        
          9 using namespace std;10 11 const int MAXN = 1e5 + 10;12 const int INF = 0x3f3f3f3f;13 int a[MAXN];14 int n, m;15 16 bool check(int tot) {17     int j = 1, sum = 0;18     for (int i=1; i<=m; ++i)    {19         sum = 0;20         while (j <= n && sum + a[j] <= tot)    {21             sum += a[j++];22         }23         if (j == n + 1) return true;24     }25     return false;26 }27 28 int main(void)  {       //POJ 3273 Monthly Expense29     //freopen ("POJ_3273.in", "r", stdin);30 31     while (scanf ("%d%d", &n, &m) == 2) {32         int l = 0, r = 0;33         for (int i=1; i<=n; ++i)    {34             scanf ("%d", &a[i]);35             if (l < a[i])   l = a[i];36             r += a[i];37         }38 39         while (l < r)   {40             int mid = (l + r) >> 1;41             if (check (mid))    r = mid;42             else    l = mid + 1;43         }44         printf ("%d\n", l);45     }46 47     return 0;48 }