【SHOI2015】自动刷题机

一道朴素的二分题，二分的基础很不好所以选择了这道

本道题主要进行二分的考察

容易发现，对于给定的序列，n越大能过的题是越少的，所以可以二分来求刚好过k道题的左右边界。

若mid大于k,即做得太多了，就将l右移。

若mid小于k,即做得太少了，就将r左移。

代码实现：

#include<bits/stdc++.h>
using namespace std;
int n,k; 
const int maxn=1e6+10;
long long a[maxn];
long long check(long long id)
{
	long long sum=0;
	long long ans=0;
	for(int i=1;i<=n;i++)
	{
		sum=max(sum+a[i],0ll);
		if(sum>=id)
		{
			ans++;
			sum=0;
		}
	}
	return ans;
}
long long l=1;
long long r=1e18;
long long ans1=-1;
long long ans2=-1;
int main()
{
	cin>>n>>k;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
	}
	while(l<=r)
	{
		long long mid=(l+r)>>1;
		long long p=check(mid);
	
		if(p<=k)
		{
			r=mid-1;
			if(p==k)
			{
				ans1=mid;
			}
		}
		else l=mid+1;
	}
	l=1;
	r=1e18;
	while(l<=r)
	{
		long long mid=(l+r)>>1;
		long long p=check(mid);
		if(p>=k)
		{
			l=mid+1;
			if(p==k)
			{
				ans2=mid;
			}
		}
		else r=mid-1;
	}
	if(ans1==-1)
	{
		puts("-1");
	}
	else cout<<ans1<<" "<<ans2;
}