[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;
}