P4343 [SHOI2015]自动刷题机()

https://www.luogu.com.cn/problem/P4343

#include <iostream>
using namespace std ; const int N=1e5+2;
 #define int long long
 const int inf=1e15;
 int a[N],n,m;
 
 int cal(int x){
	int t=0,s=0; 
    for(int i=1;i<=n;i++){
        s=max(s+a[i],0ll);
        if(s>=x) s=0,t++;
    }
	return t;
}
 void solve(){
 	int ans1=-1,ans2=-1 ;
 	int t;
	int l,r,md;
 	l=1,r=inf;
 	while(l<=r){
		md=(l+r)/2;
 		if((t=cal(md))<=m){
 		   r=md-1; 
		   if(t==m) ans1=md;	
		 }
 		else l=md+1;
	}
	
	l=1,r=inf;
 	while(l<=r){
 		md=(l+r)/2;
 		if((t=cal(md))>=m){
 		   l=md+1; 
 		   if(t==m) ans2=md;	
		 }
 		else r=md-1;
	 }
	 if(ans1==-1) cout<<-1<<endl;
	 else cout<<ans1<<' '<<ans2<<endl;
 }
 
 signed main(){
 	cin>>n>>m;
 	for(int i=1;i<=n;i++) cin>>a[i];
 	solve();
 }
————————

https://www.luogu.com.cn/problem/P4343

#include <iostream>
using namespace std ; const int N=1e5+2;
 #define int long long
 const int inf=1e15;
 int a[N],n,m;
 
 int cal(int x){
	int t=0,s=0; 
    for(int i=1;i<=n;i++){
        s=max(s+a[i],0ll);
        if(s>=x) s=0,t++;
    }
	return t;
}
 void solve(){
 	int ans1=-1,ans2=-1 ;
 	int t;
	int l,r,md;
 	l=1,r=inf;
 	while(l<=r){
		md=(l+r)/2;
 		if((t=cal(md))<=m){
 		   r=md-1; 
		   if(t==m) ans1=md;	
		 }
 		else l=md+1;
	}
	
	l=1,r=inf;
 	while(l<=r){
 		md=(l+r)/2;
 		if((t=cal(md))>=m){
 		   l=md+1; 
 		   if(t==m) ans2=md;	
		 }
 		else r=md-1;
	 }
	 if(ans1==-1) cout<<-1<<endl;
	 else cout<<ans1<<' '<<ans2<<endl;
 }
 
 signed main(){
 	cin>>n>>m;
 	for(int i=1;i<=n;i++) cin>>a[i];
 	solve();
 }