欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

bzoj 4590: [Shoi2015]自动刷题机

程序员文章站 2022-03-15 10:18:34
...

简述题意:

Description

自动刷题机的代码生成模块会有两种可能的结果:

A.写了x行代码。

B.删掉了之前写的y行代码。(如果y大于当前代码长度则相当于全部删除。)

对于所有题目,存在固定的长度n>0。一旦自动刷题积累了大于等于n行的代码,它就会自动提交并AC此题,然后新建一个文件开始写下一题。SHTSC得到了关于写代码的日志信息。但是他不知道n是多少。但他知道一共AC了k道题,希望你计算n可能的最小值和最大值。

Input

第一行两个整数l,k,表示刷题机的日志一共有l行,一共了切了k题。

第二行l个整数,x1…xl。xi>=0表示写了xi行代码。xi<0表示删除了这道题的-xi行代码。

1<=l,k<=100000,|xi|<=10^9

Output

输出两个数a,b。分别代表n可能的最小值和最大值。如果不存在这样的n则输出-1。

------------------------------------------------------------------------------------------------------------------------------------------------------------------------                                                                                                                                                                                             

算法:二分查找+模拟

时间复杂度::O(logn)

题解:我们通过打表找规律可以发现,当日志一定时,如果n越大,那么k越小。(即:n与k之间满足单调性)

所以我们通过二分查找来确定最优解(注意 二分的正确姿势)

最后再对ans1,ans2检验一下即可!

代码如下:

#include <cstdio>
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <queue>
#define ll long long
#define N 100005
using namespace std;
int a[N];
int n,k;
ll check(ll x)
{
	ll sum=0;
	ll cnt=0;
	for(int i = 1;i <= n;i++)
	{
		sum=max(0ll,sum+a[i]);//这个地方要注意! 
		if(sum>=x) cnt++,sum=0;
	}
	return cnt;
}
int main()
{
	scanf("%d%d",&n,&k);
	for(int i = 1;i <= n;i++)
	{
		scanf("%d",&a[i]);
	}
	ll l1=1,r1=100000000000000000ll;
	ll ans1;
	while(l1<=r1)
	{
 		ll mid=(l1+r1)/2;
		if(check(mid)<=k) r1=mid-1,ans1=mid;
		else l1=mid+1;
	}
	ll l2=1,r2=100000000000000000ll;
	ll ans2;
	while(l2<=r2)
	{
		ll mid=(l2+r2)/2;
		if(check(mid)>=k) l2=mid+1,ans2=mid;
		else r2=mid-1;
	}
	if((check(ans1)!=k)||(check(ans2)!=k)) 
	{
		puts("-1");
		exit(0);
	}else
	{
		printf("%lld %lld\n",ans1,ans2);
	}
	return 0 ;
}
 

 

相关标签: 二分查找