描述
高考结束后，同学们大都找到了一份临时工作，渴望挣得一些零用钱。从今天起，Matrix67将连续工作N天(1<=N<=100 000)。每一天末他可以领取当天及前面若干天里没有领取的工资，但他总共只有M(1<=M<=N)次领取工资的机会。Matrix67已经知道了在接下来的这N天里每一天他可以赚多少钱。为了避免自己滥用零花钱，他希望知道如何安排领取工资的时间才能使得领到工资最多的那一次工资数额最小。注意Matrix67必须恰好领工资M次，且需要将所有的工资全部领走（即最后一天末需要领一次工资）。
输入
第一行输入两个用空格隔开的正整数N和M
以下N行每行一个不超过10000正整数，依次表示每一天的薪水。
输出
输出领取到的工资的最大值最小是多少。
输入样例 1
7 5
100
400
300
100
500
101
400
输出样例 1
500
提示
【样例说明】
采取下面的方案可以使每次领到的工资不会多于500。这个答案不能再少了。
100 400 300 100 500 101 400 每一天的薪水
<------1 <-------2 <---3 <---4 <---5 领取工资的时间
500 400 500 101 400 领取到的工资
老是想着用dp
之前做过一次最大值的最小值二分答案 以后一定要引起警觉
二分答案的时候出现了很多小错误
有以下两种写法要注意：
#include<bits/stdc++.h>
using namespace std;
//input
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define RI(n) scanf("%d",&(n))
#define RII(n,m) scanf("%d%d",&n,&m);
#define RIII(n,m,k) scanf("%d%d%d",&n,&m,&k)
#define RS(s) scanf("%s",s);
#define LL long long
#define REP(i,N) for(int i=0;i<(N);i++)
#define CLR(A,v) memset(A,v,sizeof A)
//////////////////////////////////
#define N 100005
int a[N];
int main()
{
int n,m;
RII(n,m);
long sum=;
int maxx=;
rep(i,,n)
{
RI(a[i]);
sum+=a[i];
maxx=max(maxx,a[i]);
}
long long L=maxx;
long long R=sum;
int ans;
while(L<R)
{
long long sum=;
long long mid=(L+R)>>; int cnt=;
rep(i,,n)
{
if(sum+a[i]>mid)
{
cnt++;sum=a[i];
}
else
sum+=a[i];
}
if(sum)cnt++; if(cnt>m)L=mid+;
else R=mid; //如果写成这样就会错 因为mid是趋向左的 如果L和M差1 那么将进入死循环
if(cnt>=m)L=mid;
else R=mid-;
}
cout<<R;
}
#include<bits/stdc++.h>
using namespace std;
//input
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define RI(n) scanf("%d",&(n))
#define RII(n,m) scanf("%d%d",&n,&m);
#define RIII(n,m,k) scanf("%d%d%d",&n,&m,&k)
#define RS(s) scanf("%s",s);
#define LL long long
#define REP(i,N) for(int i=0;i<(N);i++)
#define CLR(A,v) memset(A,v,sizeof A)
//////////////////////////////////
#define N 100005
int a[N]; int main()
{
int n,m;
RII(n,m);
long sum=;
int maxx=;
rep(i,,n)
{
RI(a[i]);
sum+=a[i];
maxx=max(maxx,a[i]);
} long long L=maxx;
long long R=sum;
int ans;
while(L<=R)
{
int cnt=;
long long sum=;
long long mid=(L+R)>>; rep(i,,n)
{
if(sum+a[i]>mid)
{
cnt++;sum=a[i];
}
else
sum+=a[i];
}
if(sum)cnt++; if(cnt>m)L=mid+;
else ans=mid,R=mid-; }
cout<<ans; }