题目描述
曾经发明了信号增幅仪的发明家 SHTSC 又公开了他的新发明：自动刷题机——一种可以自动 AC 题目的神秘装置。
自动刷题机刷题的方式非常简单：首先会瞬间得出题目的正确做法，然后开始写程序。每秒，自动刷题机的代码生成模块会有两种可能的结果：
1.写了xx行代码
2.心情不好，删掉了之前写的yy行代码。（如果yy大于当前代码长度则相当于全部删除。）
对于一个 OJ，存在某个固定的长度n>0n>0，一旦自动刷题机在某秒结束时积累了大于等于nn行的代码，它就会自动提交并 AC 此题，然后新建一个文件（即弃置之前的所有代码）并开始写下一题。SHTSC 在某个 OJ 上跑了一天的自动刷题机，得到了很多条关于写代码的日志信息。他突然发现自己没有记录这个 OJ 的nn究竟是多少。所幸他通过自己在 OJ 上的 Rank 知道了自动刷题机一共切了kk道题，希望你计算nn可能的最小值和最大值。
输入格式
第一行两个整数ll,kk，表示刷题机的日志一共有ll行，一共了切了kk题。
第二行ll个整数x_i≥0表示写了x_i行代码，x_i<0代表删除了这道题的-x_i行代码。
输出格式
输出两个数aa,bb，分别代表nn可能的最小值和最大值。如果不存在这样的nn则输出-1−1。
#include<queue>
#include<cmath>
#include<vector>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define ll long long
#define int long long
using namespace std;
const int N=1e5+100;
ll a[N];
int l,k;
bool Mincheck(int x){
int now=0,ans=0;
for(int i=1;i<=l;i++){
now+=a[i];
if(now>=x)ans++,now=0;
now=max((ll)0,now);
}
if(ans<=k)return 1;
else return 0;
}
bool Maxcheck(int x){
int now=0,ans=0;
for(int i=1;i<=l;i++){
now+=a[i];
if(now>=x)ans++,now=0;
now=max((ll)0,now);
}
if(ans>=k)return 1;
else return 0;
}
signed main(){
cin>>l>>k;
int Max=0;
for(int i=1;i<=l;i++){
scanf("%lld",&a[i]);
Max+=abs(a[i]);
}
if(l<k){
cout<<-1<<endl;
return 0;
}
int l=1,r=Max,ans=-1;
while(l<=r){
int mid=(l+r)>>1;
if(Mincheck(mid)){
r=mid-1;
ans=mid;
}else{
l=mid+1;
}
}
if(ans==-1){
printf("-1
");
return 0;
}
int op=ans;
ans=-1;
l=1,r=Max;
while(l<=r){
int mid=(l+r)>>1;
if(Maxcheck(mid)){
l=mid+1;
ans=mid;
}else{
r=mid-1;
}
}
if(ans<op){
cout<<-1<<endl;
return 0;
}else
cout<<op<<' '<<ans<<endl;
}