BZOJ 4590 [Shoi2015]自动刷题机

题目大意

给你一个数，初始值为0,每单位时间可以将这个数加上一个数（可以使负数），每单位时间结束之后如果这个数大于一个特定值结果+1.现在给你这个结果，问达成这个结果的最小阈值和最大阈值。

看到最大和最小，再看看数据范围和题面……基本可以猜到是二分答案。最终的结果和阈值关系很大——阈值大了就会使得结果变小，反之同理。所以二分一下就好了。

注意用long long。还有一点特别重要就是初始值一定要定准！阈值不可以是0！原来我都是忽视初始值的但是现在发现不能想当然的去初始化.

还有一点就是-1的判断。这题判断可行情况直接试一试答案的l和r可行不可行就可以了。

#include <cstdio>
#include <algorithm>
using namespace std;
long long n,k,v[100010];
long long l,r,mid,rl,rr;
long long check(long long x)
{
	long long tmp=0,ret=0;
	for(int i=1;i<=n;++i)
	{
		tmp=max(0ll,tmp+v[i]);
		if(tmp>=x) tmp=0,ret++;
	}
	return ret;
}
int main()
{
	scanf("%lld%lld",&n,&k);
	for(int i=1;i<=n;++i) scanf("%lld",v+i);
	l=1,r=1000000000000000000ll;
	while(l<r)
	{
		mid=(l+r)>>1;
		if(check(mid)>=k) l=mid+1;
		else r=mid;
	}
	rr=l-1;
	l=1,r=1000000000000000000ll;
	while(l<r)
	{
		mid=(l+r)>>1;
		if(check(mid)<=k) r=mid;
		else l=mid+1;
	}
	rl=r;
	if(check(rl)!=k||check(rr)!=k) printf("-1\n");
	else printf("%lld %lld\n",rl,rr);
	return 0;
}