工资

(money/money.in/money.out)
时限1000ms 内存256MB
聪哥在暑假参加了打零工的活动，这个活动分为n个工作日，每个工作日的工资为Vi。有m个结算工钱的时间,聪哥可以自由安排这些时间，也就是说什么时候拿钱，老板说的不算，聪哥才有发言权！（因为聪哥是土豪，他是老板的老板）
聪哥不喜欢身上一次性有太多的钱，于是他想安排一下拿钱的时间，使他一次性拿的钱中最大的最小。（最后一天一定要领钱）
输入
第一行 2个数 n,m
接下来n行，每行一个数，代表Vi.
输出
最小的最大钱数。
样例输入
7 5
100
400
300
100
500
101
400
样例输出
500
样例说明 
100 400//300 100//500//101//400// 
“//”表示老大要去拿钱。
数据范围
20%   1<=n<=20
另 20%  1<=n<=50,Vi的和不超过1000
100%  1<=n<=100,000,m<=n,Vi<=10,000

明显，二分答案，是的最大的区间段和最小

还有一个限制条件，最后一天必须结算

判断的时候加以分析就好了

分值:100/100

#include 
#include
#include
#include<string>
#include
#include
#include
#define ll long long
#define DB double
using namespace std;
inline int read()
{
    int x=0,w=1;char ch=getchar();
    while(!isdigit(ch)){ if(ch=='-') w=-1;ch=getchar();}
    while(isdigit(ch)) x=(x<<3)+(x<<1)+ch-'0',ch=getchar();
    return x*w;
}
const int N=1e5+100;
int n,m,a[N],M;
ll ans,L,R,mid,k;
bool v[N];
bool ok(ll x)
{
    M=0;k=0;v[n]=0;
    for(int i=1;i<=n;++i)
    {
        if(xreturn 0;
        k+=a[i];
        if(k>x) M++,k=a[i],v[i-1]=1;
//        cout<
        if(M>m) return 0;
    }
    if(k>x) return 0;
//    cout<
    if(!v[n]){v[n]=1;M++;}
    if(M<=m) return 1;
    return 0;
}
int main()
{
    freopen("money.in","r",stdin);
    freopen("money.out","w",stdout);
    n=read();m=read();
    for(int i=1;i<=n;++i) a[i]=read(),R+=a[i];
//    cout<
    while(L<=R)
    {
        mid=(L+R)>>1;
        if(ok(mid)) ans=mid,R=mid-1;
        else L=mid+1;
    }
    printf("%lld",ans);
    return 0;
}