题目描述
SHTSC发明了一种自动刷题机,它刷题的方式非常简单:首先会瞬间得出题目的正确做法,然后开始写程序。每秒,自动刷题机的代码生成模块会有两种可能的结果:
1.写了\(x\)行代码
2.心情不好,删掉了之前写的\(y\)行代码。(如果\(y\)大于当前代码长度则相当于全部删除。)
对于一个 OJ,存在某个固定的长度\(n>0\),一旦自动刷题机在某秒结束时积累了大于等于\(n\)行的代码,它就会自动提交并 AC 此题,然后新建一个文件(即弃置之前的所有代码)并开始写下一题。SHTSC 在某个 OJ 上跑了一天的自动刷题机,得到了很多条关于写代码的日志信息。他突然发现自己没有记录这个 OJ 的\(n\)究竟是多少。所幸他通过自己在 OJ 上的 Rank 知道了自动刷题机一共切了\(k\)道题,希望你计算\(n\)可能的最小值和最大值。
Links
Solution
本题显而易见的就是一道基本的二分,用两次二分,一次求最小值,一次求最大值,就可以了
Code
#include<bits/stdc++.h>
#include<climits>
const int maxn = 100001;
using namespace std;
int code[maxn];
int l,k;
int check(long long len){ //若长度为len时提交则可以AC的题目数量
long long sum = 0;
int ac = 0;
for(int i = 1; i <= l; i++){
sum += code[i];
if(sum < 0){ sum = 0;continue;}
else if(sum >= len) ++ac,sum = 0;
}
return ac;
}
long long BinSearch(){ //二分查找最大
long long left = 0,right = LLONG_MAX;
long long ans = -1;
long long mid;
while(left + 1 < right){
mid = (left + right) / 2;
int len = check(mid);
if(len == k) ans = mid;
if(len >= k) left = mid;
else right = mid;
}
return ans;
}
int main(){
scanf("%d%d",&l,&k);
for(int i = 1; i <= l; i++){
scanf("%d",&code[i]);
}
long long max = BinSearch(); //二分求最大值
if(max == -1){ //如果最大值为-1,则无解,直接输出-1结束程序
printf("-1");
return 0;
}
k++;
long long min = BinSearch() + 1;//二分求最小值(即切掉k+1道题时的最大值+1)
if(min == 0) min++;
printf("%lld %lld",min,max);
return 0;
}