二分搜索 POJ 3273 Monthly Expense

 

题目传送门

1 /* 2 题意：分成m个集合，使最大的集合值(求和)最小 3 二分搜索：二分集合大小，判断能否有m个集合。 4 */ 5 #include <cstdio> 6 #include <algorithm> 7 #include <cstring> 8 #include <cmath> 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 Expense 29 //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 }

 

转载于:https://www.cnblogs.com/Running-Time/p/4676376.html

总结

以上是生活随笔为你收集整理的二分搜索 POJ 3273 Monthly Expense的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。