【SHOI2015】自動刷題機

一道樸素的二分題，二分的基礎很不好所以選擇了這道

本道題主要進行二分的考察

容易發(fā)現，對于給定的序列，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;
}