1. 工资
(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//
“//”表示老大要去拿钱。
同bzoj1639……二分
我的r才开10w，结果只有70……
#include<cstdio>
int n,m,l,r,ans;
int a[100010];
int s[100010];
inline int max(int a,int b)
{return a>b?a:b;}
inline int read()
{
int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
inline bool jud(int k)
{
int sum,piece=m-1,now=1;
while (piece&&now<=n)
{
sum=0;
while (now<=n&&sum+a[now]<=k) sum+=a[now++];
piece--;
}
if (now<=n&&s[n]-s[now-1]>k) return 0;
return 1;
}
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();
s[i]=s[i-1]+a[i];
l=max(l,a[i]);
}
r=10000000;
while (l<=r)
{
int mid=(l+r)>>1;
if (jud(mid)){ans=mid;r=mid-1;}
else l=mid+1;
}
printf("%d
",ans);
}