从花费最小到 总的花费开始二分
每次判断 对于当前的 mid ,s[i](s 存每天花费的money的数组) 判断 可以分成多少段 <= mid
(假设 s[1] + s[2} <= mid s[1] + s[2] + s[3] > mid 那么s[1] + s[2] 就为一段)
只要分成的段数小于等于m 那么对于当前mid 就可以 满足 分成m 段 并且 最大值为mid;
(因为段数少于m 我们可以将其中的几段进行拆分,一定能满足 各段 <= mid)
#include <cstdio> #include <cstring> #include <iostream> using namespace std; int const MAXN = 100010; int n,m,ma; int s[MAXN]; int Max(int a,int b){ return a>b?a:b; } int Min(int a,int b){ return a<b?a:b; } bool Judge(int mid){ int s1 = 0,flag = 0; for(int i = 0;i < n;i++){ if(s[i] > mid) return false; if(s1 + s[i] <= mid) s1 += s[i]; else{ s1 = s[i]; flag++; } } if(flag < m) return true; return false; } void Search(int l,int r){ int s1; while(l <= r){ int mid = (l + r) / 2; if(Judge(mid)) s1 = mid, r = mid - 1; else l = mid + 1; } printf("%d\n",s1); } int main(){ while(~scanf("%d%d",&n,&m)){ int l = MAXN, r = 0; for(int i = 0;i < n;i++){ scanf("%d",&s[i]); l = Min(l,s[i]); r += s[i]; } ma = MAXN; Search(l,r); } return 0; }