【二分答案】買禮物的艱辛

小X同學給小C同學選了N件禮物，決定順序購買并贈送，但作為一個沒有工資沒有零花錢的可憐小朋友，有M位好心的同學伸出了援助之手，然而為了減少最高的借款量，小X同學希望OI競賽的你為他合理規劃，使得他能輕松快樂地送出禮物。

Input

第一行輸入兩個用空格隔開的正整數N和M

以下N行每行一個不超過10000正整數，依次表示禮物的價格。

Output

一個整數，即最高借款量。

題目有bug，然而實際上是m+1個人，然後我就A了。。。

答案的範圍在最大的a[i]到所有a[i]的和之間，然後二分mid。

按順序取，如果能借mid或mid以内的錢話r=mid，否則l=mid+1

輸出答案。

#include<cstdio>
#include<iostream>
using namespace std; 
int n,m,a[100001],l;
long long r,mid;
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;++i){
		scanf("%d",&a[i]);
		r+=a[i];
		l=max(l,a[i]);
	}
	++m;
	while(l<r){       //二分
		mid=(l+r)/2;
		long long s=0,k=0,lq=0,lr=0;
		while(k<n){   
			++k;   //取到第k個
			if(lq+a[k]<=mid) lq+=a[k];   //累計取了多少，然後有沒有超過
			else{   //如果超過了，那麼就把這些禮物結算給一個人
				lr++;   //多一個人要借
				lq=0;   //清下零
				if(lr>m) break;   //如果沒人可借，退出
				--k;   //避免跳過計算
			}
		}
		if(lq>0) lr++;   //如果有多餘的沒結算
		if(lr>m) l=mid+1;   //判斷是否借得到
		else r=mid;
	}
	printf("%d",l);
}