分析:
这道题很恶心...那个-1卡了我一会儿,其他的部分很简单。
我们能够看出,解题个数和n相关,并且形成不下降序列,那么我们可以二分找到第一个满足解题数为K和最后一个满足解题数为K的位置
判断两件事,(1)check(1)>=k(2)ans1<=ans2
附上代码:
#include#include #include #include #include #include #include using namespace std;#define N 100005#define ll long longint 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) >1; if(check(m)>k)l=m+1; else r=m; } ll ans=l; l=1,r=1ll<<60; while(l >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;}