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

[bzoj]4590: [Shoi2015]自动刷题机

程序员文章站 2024-03-20 17:23:28
...

二分答案,暴力验证。找到一个最小满足的值与一个最大满足的值。

记得最后判断二分的是否正确。

#include <cstdio>
#include <algorithm>
#define ll long long
using namespace std;
int n,k;
ll w[100005];
ll sum,x,y;
inline ll pd(ll x)
{
	register int i;
	ll now=0,ret=0;
	for (i=1;i<=n;i++)
	{
		now+=w[i];
		if (now<0) now=0;
		if (now>=x) ret++,now=0;
	}
	return ret;
}
inline ll efmi(ll l,ll r)
{
	ll mid,ret=0;
	while (l<=r)
	{
		mid=(l+r)>>1;
		if (pd(mid)<=k) r=mid-1,ret=mid;
		else l=mid+1;
	}
	return ret;
}
inline ll efma(ll l,ll r)
{
	ll mid,ret=0;
	while (l<=r)
	{
		mid=(l+r)>>1;
		if (pd(mid)>=k) l=mid+1,ret=mid;
		else r=mid-1;
	}
	return ret;
}
int main()
{
	register int i,j;
	scanf("%d %d",&n,&k);
	for (i=1;i<=n;i++)
	{
		scanf("%lld",&w[i]);
		sum+=abs(w[i]);
	}
	x=efmi(1,sum);y=efma(1,sum);
	if (pd(x)!=k||pd(y)!=k) printf("-1");
	else printf("%lld %lld",x,y);
	return 0;
}