80分求助!
查看原帖
80分求助!
716721
leo12334楼主2023/1/2 16:34

求助各位大佬,测试点10 11 17 18 wa了,照着题解改了几个坑,不同的是我是先找n的最大值,然后以n的最大值为右边界进行查找,不知道问题出在哪里QWQ

#include<bits/stdc++.h>
using namespace std;
#define maxn 123456
#define ll long long 
int n,k,maxx=-1,minn;
ll a[maxn],l,r,mid;
ll fun(ll x){
	ll now=0,cnt=0;
	for(int i=1;i<=n;i++){
		if(a[i]>0){
			now+=a[i];
			if(now>=x){
				now=0;
				cnt++;
			}
		}
		else if(a[i]<=0){
			now+=a[i];
			ll zero=0;
			now=max(now,zero);
		}
	}
//	cout<<l<<' '<<mid<<' '<<r<<' '<<cnt<<endl;
	return cnt;
}
int main(){
	cin>>n>>k;
	for(int i=1;i<=n;i++)cin>>a[i];
	l=1;r=1e18;
	while(l<=r){
		mid=(r+l)/2;
		if(fun(mid)-k>0)l=mid+1;  //定的标准太低,找右边界 
		else if(fun(mid)==k){maxx=mid;l=mid+1;}//更新答案 
		else r=mid-1;  //标准太高,在左半边找 
	}
	r=l;l=1;//以n的最大值为查找边界 
//	puts(" "); 
	while(l<=r){
		mid=(r+l)/2;
		if(fun(mid)-k>0)l=mid+1; //定的标准太低 
		else if(fun(mid)==k){minn=mid;r=mid-1;}
		else r=mid-1; //找左边界 
	}
	if(maxx==-1)cout<<"-1"<<endl;
	else cout<<minn<<' '<<maxx<<endl;
}
2023/1/2 16:34
加载中...