题目：https://www.luogu.org/problemnew/show/P1182
题意：
有n个数，要分成连续的m段。将每段中的数相加，问之和的最大值的最小值是多少。
思路：
和P1316丢瓶盖很像，就是反一下而已。
同样是二分答案，然后检查一下当前的答案可不可行，如果可行由于需要得到最小值，所以缩小上界。
要注意的点是，st的初始化应该是num中的最大值而不是随意给一个0
这会影响到分段的计数。
如果当前值是比某一个num要小的话，cnt还是+1了。
1 #include<stdio.h> 2 #include<stdlib.h> 3 #include<map> 4 #include<set> 5 #include<iostream> 6 #include<cstring> 7 #include<algorithm> 8 #include<vector> 9 #include<cmath> 10 #include<queue> 11 12 #define inf 0x7fffffff 13 using namespace std; 14 typedef long long LL; 15 typedef pair<int, int> pr; 16 17 int n, m; 18 const int maxn = 1e5 + 5; 19 int num[maxn]; 20 21 bool check(int x) 22 { 23 int cnt = 0; 24 int tot = 0; 25 for(int i = 1; i <= n; i++){ 26 if(tot + num[i] <= x){ 27 tot += num[i]; 28 } 29 else{ 30 tot = num[i]; 31 cnt++; 32 } 33 } 34 if(tot <= x)cnt++; 35 if(cnt <= m)return true; 36 else return false; 37 } 38 39 int main() 40 { 41 scanf("%d%d", &n, &m); 42 int st = 0, ed = 0; 43 for(int i = 1; i <= n; i++){ 44 scanf("%d", &num[i]); 45 ed += num[i]; 46 st = max(st, num[i]); 47 } 48 int ans; 49 while(st <= ed){ 50 int mid = (st + ed) / 2; 51 if(check(mid)){ 52 ed = mid - 1; 53 ans = mid; 54 } 55 else{ 56 st = mid + 1; 57 } 58 } 59 printf("%d\n", st); 60 return 0; 61 }
---恢复内容结束---
原文：https://www.cnblogs.com/wyboooo/p/10386266.html