无解应该怎么爬判断呢,这样直接判断是否为边界好像不行
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int maxn=1e6+10;
int l,k;
int a[maxn];
bool check1(int mid) {
int sum=0;
int cnt=0;
for(int i=1; i<=l; i++) {
// {cout<<"sum和mid"<<sum<<" "<<mid<<endl;
// cout<<a[i]<<endl;
if(a[i]>0) {
sum+=a[i];
if(sum>=mid) {
sum=0;
cnt++;
}
}
else if(a[i]<0) {
if(sum+a[i]<0) {
sum=0;
} else if(a[i]+sum>0) {
sum+=a[i];
}
}
}
// cout<<cnt<<endl;
return cnt<=k?true:false;
}
bool check2(int mid) {
int sum=0;
int cnt=0;
for(int i=1; i<=l; i++) {
if(a[i]>0) {
sum+=a[i];
if(sum>=mid) {
sum=0;
cnt++;
}
}
else if(a[i]<0) {
if(sum+a[i]<0) {
sum=0;
} else if(a[i]+sum>0) {
sum+=a[i];
}
}
}
return cnt>=k?true:false;
}
int bs1(int l,int r) {
while(l<r) {
int mid=(l+r)/2 ;
// cout<<"mid="<<mid<<endl;
if(check1(mid))
r=mid;
else
l=mid+1;
}
return l;
}
int bs2(int l,int r) {
while(l<r) {
int mid=(l+r+1)/2 ;
if(check2(mid))
l=mid;
else
r=mid-1;
}
return l;
}
signed main() {
cin>>l>>k;
for(int i=1; i<=l; i++) {
cin>>a[i];
}
if(bs1(1,1e18+1)==1||bs2(-1,1e18+1)==1e18+1)
cout<<"-1";
else
cout<<bs1(1,1e18+1)<<" "<<bs2(1,1e18+1);
return 0;
}