分析:
这道题很恶心...那个-1卡了我一会儿,其他的部分很简单。
我们能够看出,解题个数和n相关,并且形成不下降序列,那么我们可以二分找到第一个满足解题数为K和最后一个满足解题数为K的位置
判断两件事,(1)check(1)>=k(2)ans1<=ans2
附上代码:
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <queue>
using namespace std;
#define N 100005
#define ll long long
int a[N],l,k;
int check(ll x)
{
ll t=0;
int num=0;
for(int i=1;i<=l;i++)
{
t=max(t+a[i],0ll);
if(t>=x)t=0,num++;
}
return num;
}
int main()
{
scanf("%d%d",&l,&k);
for(int i=1;i<=l;i++)
{
scanf("%d",&a[i]);
}
if(check(1)<k)
{
puts("-1");
return 0;
}
ll l=1,r=1ll<<60;
while(l<r)
{
ll m=(l+r)>>1;
if(check(m)>k)l=m+1;
else r=m;
}
ll ans=l;
l=1,r=1ll<<60;
while(l<r)
{
ll m=(l+r)>>1;
if(check(m)>=k)l=m+1;
else r=m;
}
if(ans>l-1)
{
puts("-1");
return 0;
}
printf("%lld %lld\n",ans,l-1);
return 0;
}