题目背景
曾经发明了信号增幅仪的发明家 SHTSC 又公开了他的新发明：自动刷题机——一种可以自动 AC 题目的神秘装置。
题目描述
自动刷题机刷题的方式非常简单：首先会瞬间得出题目的正确做法，然后开始写程序。每秒，自动刷题机的代码生成模块会有两种可能的结果：
1.写了 x 行代码
2.心情不好，删掉了之前写的 y 行代码。（如果 y 大于当前代码长度则相当于全部删除。）
对于一个 OJ，存在某个固定的正整数长度 n，一旦自动刷题机在某秒结束时积累了大于等于 n 行的代码，它就会自动提交并 AC 此题，然后新建一个文件（即弃置之前的所有代码）并开始写下一题。SHTSC 在某个 OJ 上跑了一天的自动刷题机，得到了很多条关于写代码的日志信息。他突然发现自己没有记录这个 OJ 的 n 究竟是多少。所幸他通过自己在 OJ 上的 Rank 知道了自动刷题机一共切了 k 道题，希望你计算 n 可能的最小值和最大值。
输入格式
第一行两个整数 l,k，表示刷题机的日志一共有 l 行，一共了切了 k 题。
接下来 l 行，每行一个整数 xi，依次表示每条日志。若 xi≥0，则表示写了 xi 行代码，若 xi<0，则表示删除了 −xi 行代码。
输出格式
输出一行两个整数，分别表示 n 可能的最小值和最大值。
如果这样的 n 不存在，请输出一行一个整数 −1。
输入输出样例
输入 #1
4 2
2
5
-3
9输出 #1
3 7说明/提示
数据规模与约定
- 对于 20% 的数据，保证 l≤10；
- 对于 40% 的数据，保证 l≤100 ；
- 对于 60% 的数据，保证l≤2×103；
- 对于 100% 的数据，保证 1≤l≤105，−109≤xi≤109。
解题思路（小tips）
本题的逻辑思维较简单 但需要二分本身具有足够的认识 否则容易混乱 搞不清出如何迭代
check函数的内层逻辑也很简单 就是直接模拟 返回切题的计数即可
所以本题最大的难点就在于两次二分的过程
当然也有的题解是进行一次二分 然后直接递增或递减 检查每一个数是否满足check 知道找到不符合即另一个边界即可 但因为是二分的专项练习 所以我们这里只提供两次二分的思路解析和代码
具体的代码思路部分为
while(l<=r){
LL mid=l+r>>1;
if(check(mid)<m) r=mid-1;
else if(check(mid)>m) l=mid+1;
else ans1=mid,r=mid-1;
}
这么写的思路 也很简单 ：切题数不足 则是阈值过大 直接缩小右边界 从而减小下次迭代的mid答案阈值 反之亦然 恰好相等时即找到答案
但是也有读者说 我的二分模板是这样的
为什么最终答案不同或者只能找到一个边界
while(l<r){
LL mid=l+r>>1;
if(check(mid)<=m) r=mid;
else l=mid+1;
}
这里其实是因为 题目中要求的是切题数必须恰好等于k的 交题阈值的最大最小值 而上面的模板在寻找时的边界是<= 或者>= 其实找到的是能够切题数>=m的最右答案 和切题数<=m的最左答案 而非＝m时的最左最右答案
AC代码展示
如果觉得有用 就点赞+收藏 关注一下吧
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long LL;
const int N=1e5+5;
LL n,m,a[N];
LL check(LL x){
LL sum=0,cnt=0;
for(int i=1;i<=n;i++){
sum+=a[i];
if(sum<0) sum=0;
if(sum>=x) cnt++,sum=0;
}
return cnt;
}
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++) cin>>a[i];
LL l=1,r=1e15;
LL ans1=-1;
while(l<=r){
LL mid=l+r>>1;
if(check(mid)<m) r=mid-1;
else if(check(mid)>m) l=mid+1;
else ans1=mid,r=mid-1;
}
cout<<ans1<<" ";
if(ans1==-1) return 0;
l=1,r=1e15;
LL ans2=-1;
while(l<=r){
LL mid=l+r>>1;
if(check(mid)<m) r=mid-1;
else if(check(mid)>m) l=mid+1;
else ans2=mid,l=mid+1;
}
cout<<ans2<<endl;
return 0;
}