279B - Books

A quite easy binary-search problem

Since $$$n \le 10^5$$$, the time complexity of the soulution should be either $$$O(n)$$$ or $$$O(n\cdot log_2n)$$$. That's where binary-search come in handy.

First, we should enumerate the starting point $$$i$$$ (the serial number of the book we read first) For every $$$i$$$, there is an ending point $$$j$$$ which is the number of the last book we read. We could use binary-search to find $$$j$$$ for every $$$i$$$. We can use Prefix Sum to quickly find the sum of a section

#include<cstdio>
#include<iostream>
using namespace std;
const int Maxn=100000+10,inf=0x3f3f3f3f;
int a[Maxn],s[Maxn];
int n,m,ans;
inline int read()
{
	int s=0,w=1;
	char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
	while(ch>='0' && ch<='9')s=(s<<3)+(s<<1)+(ch^48),ch=getchar();
	return s*w;
}
int main()
{
//	freopen("in.txt","r",stdin);
	n=read(),m=read();
	
	for(int i=1;i<=n;++i)
	a[i]=read(),s[i]=s[i-1]+a[i];
	
	for(int i=1;i<=n;++i)
	{
		if(a[i]>m)continue;
		int l=i,r=n;
		while(l<r)
		{
			int mid=(l+r)>>1;
			mid++;
			if(s[mid]-s[i-1]<=m)l=mid;
			else r=mid-1;
		}
		ans=max(ans,l-i+1);
	}
	printf("%d\n",ans);
	return 0;
}