TYVJ1359 收入计划

//sineMora 2016.7.9
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
using namespace std;
const int maxn = 200005;
int n,m,sum[maxn];
void input(){
    cin>>n>>m;
    int t;
    sum[0] = 0;
    for(int i = 1;i <= n;i++){
        scanf("%d",&t);
        sum[i] = sum[i-1] + t;
    }
}
bool check(int t){
    int left = m-1,add = 0;
    for(int i = 1;i <= n;i++){
        if(sum[i] - sum[i-1] > t){
            return false;
        }
        if(add + sum[i] - sum[i-1] > t){
            left--;
            add = sum[i] - sum[i-1];
        }else{
            add += sum[i] - sum[i-1];
        }
        if(left < 0) return false;
    }
    return true;
}
void div(){
    int lans = 0,rans = sum[n],mans;
    while(lans <= rans){
        mans = (lans + rans) >> 1;
        if(check(mans)){
            rans = mans - 1;
            
        }else{
            lans = mans + 1;
        }
    }
    if(check(mans)) cout<<mans;
    else cout<<mans + 1;
}
int main(){
    input();
    div();
    return 0;
}

#include<iostream>
#include<cstdio>
using namespace std;
int n,m,a[100001],sum,mx,ans;
bool jud(int x)
{
     int t=0,tot=0;
     for(int i=1;i<=n;i++)
     {
             tot+=a[i];
             if(tot>x){t++;tot=a[i];}
             if(t+1>m)return 0;
             }
     return 1;
 }
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
    {
            scanf("%d",&a[i]);
            mx=max(mx,a[i]);
            sum+=a[i];
            }
    int l=mx,r=sum;
    while(l<=r)
    {
               int mid=(l+r)>>1;
               if(jud(mid)){ans=mid;r=mid-1;}
               else l=mid+1;
               }
    printf("%d",ans);
    return 0;
}