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

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

1.写了xx行代码

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

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

Links

Luogu P4343

Solution

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

Code

#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",&amp;l,&amp;k);
	for(int i=1;i<=l;i++){
		scanf("%d",&amp;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;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注