[problem:279B]↵
↵
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 ↵
Then, we use binary-search to find $j$ for every $i$. We can use Prefix Sum to quickly find the sum of a section↵
↵
```cpp↵
#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;↵
}↵
```
↵
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
Then, we use binary-search to find $j$ for every $i$. We can use Prefix Sum to quickly find the sum of a section↵
↵
```cpp↵
#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;↵
}↵
```
