洛谷4343 [SHOI2015]自动刷题机

题意

自动刷题机每秒会增加或删除 $x$ 行代码。存在一个长度 $N > 0$ ，当 某一秒后累积的代码长度 $\geq N$ ，就会提交这个程序，并新建文件。

已知刷题机交了 $K$ 道题，求 $N$ 的最值。

秒数 $L\le 100000$ 。

题解

显然 $N$ 越小，交的题目就会越多，所以可以通过二分验证，不过只有刚好 $K$ 道的时候更新答案。

唯一麻烦的就是最小值最大值都要求，而 最小值 $=$ 提交 $K+1$ 道题的最大值 $-1$ ，所以求两次最大即可。

#include<bits/stdc++.h>
#define ll long long

using namespace std;

inline ll read()
{
    char ch=getchar(); ll f=1,x=0;
    while (ch<'0' || ch>'9') { if (ch=='-') f=-1; ch=getchar(); }
    while (ch>='0' && ch<='9') { x=x*10+ch-'0'; ch=getchar(); }
    return f*x;
}

ll n,k,ans,ans2,s[100005];

inline bool check(ll mid)
{
    ll cur=0,res=0;
    for (ll i=1;i<=n;i++) 
    {
        res+=((cur+=s[i])>=mid);
        if (cur<0 || cur>=mid) cur=0;
    }
    if (res==k) ans=mid;
    return res>=k;
}

signed main()
{
    n=read(); k=read();
    for (ll i=1;i<=n;i++) s[i]=read();
    ll l=0,r=1e18; ans=-1;
    while (l<r)
    {
        ll mid=(l+r+1)>>1;
        if (check(mid)) l=mid;
        else r=mid-1;
    }
    if (ans==-1) return 0&puts("-1");
    ans2=ans;
    k++;
    l=0,r=1e18; ans=0;
    while (l<r)
    {
        ll mid=(l+r+1)>>1;
        if (check(mid)) l=mid;
        else r=mid-1;
    }
    return !printf("%lld %lld",ans+1,ans2);
}