二分最小值和最大值
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;
const long long N=100005;
long long n,k,a[N],low,high,sum;
long long Test(long long x){
long long tx=0,nw=0;
for(long long i=1;i<=n;i++){
nw+=a[i];
if(nw<0)nw=0;
if(nw>=x){tx++;nw=0;}
}
return tx;
}
long long Low(){
long long l=1,r=sum;
while(l<=r){
long long mid=l+r>>1;
if(Test(mid)<=k)r=mid-1;
else l=mid+1;
}
return l;
}
long long High(){
long long l=1,r=sum;
while(l<=r){
long long mid=l+r>>1;
if(Test(mid)<k)r=mid-1;
else l=mid+1;
}
return r;
}
int main(){
freopen("4590.in","r",stdin);
freopen("4590.out","w",stdout);
scanf("%lld %lld",&n,&k);
for(long long i=1;i<=n;i++){scanf("%lld",&a[i]);if(a[i]>0)sum+=a[i];}
low=Low();
high=High();
if(Test(low)!=k || Test(high)!=k){puts("-1");return 0;}
printf("%lld %lld\n",low,high);
return 0;
}
评论 (0)
