4590: [Shoi2015]自动刷题机
题目：传送门
题解：
很明显的一道二分题。
对于二分性的判断：如果n越大，那么AC的题就越少，n越小，AC的题就越多，那么最大最小值都满足单调性，直接瞎搞。
PS：上界有点大...搞得我WA了一次
代码：
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
using namespace std;
typedef long long LL;
LL n,m,l,r;
LL a[];
LL check(LL x)
{
LL sum=,cnt=;
for(int i=;i<=n;i++)
{
sum+=a[i];if(sum<=)sum=;
if(sum>=x)cnt++,sum=;
}
return cnt;
}
int main()
{
scanf("%lld%lld",&n,&m);
for(int i=;i<=n;i++)scanf("%lld",&a[i]);
LL ans1=,ans2=;
l=;r=1e15;
while(l<=r)
{
LL mid=(l+r)/;
if(check(mid)>m)l=mid+,ans1=mid;
else r=mid-;
}
l=;r=1e15;
while(l<=r)
{
LL mid=(l+r)/;
if(check(mid)<m)r=mid-,ans2=mid;
else l=mid+;
}
ans1++,ans2--;
if(check(ans1)!=m || check(ans2)!=m)printf("-1\n");
else printf("%lld %lld\n",ans1,ans2);
return ;
}