「SHOI2015」自动刷题机-二分查找

题目描述

SHTSC发明了一种自动刷题机,它刷题的方式非常简单:首先会瞬间得出题目的正确做法,然后开始写程序。每秒,自动刷题机的代码生成模块会有两种可能的结果:

1.写了$x$行代码

2.心情不好,删掉了之前写的$y$行代码。(如果$y$大于当前代码长度则相当于全部删除。)

对于一个 OJ,存在某个固定的长度$n>0$,一旦自动刷题机在某秒结束时积累了大于等于$n$行的代码,它就会自动提交并 AC 此题,然后新建一个文件(即弃置之前的所有代码)并开始写下一题。SHTSC 在某个 OJ 上跑了一天的自动刷题机,得到了很多条关于写代码的日志信息。他突然发现自己没有记录这个 OJ 的$n$究竟是多少。所幸他通过自己在 OJ 上的 Rank 知道了自动刷题机一共切了$k$道题,希望你计算$n$可能的最小值和最大值。

Luogu P4343

Solution

本题显而易见的就是一道基本的二分查找,用两次二分,一次求最小值,一次求最大值,就可以了

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#include<cstdio>
#include<algorithm>
#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;
}