分析:
这道题很恶心... 那个 - 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;
- }
来源: http://www.bubuko.com/infodetail-2591473.html