求助各位大佬,测试点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;
}