Codeforces 279B Books Soulution
Разница между en1 и en2, 16 символ(ов) изменены
[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;↵
}↵
```

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en3 Английский Priori_Incantatem 2020-01-24 06:27:09 31
en2 Английский Priori_Incantatem 2020-01-24 06:26:31 16
en1 Английский Priori_Incantatem 2020-01-24 06:24:22 1252 Initial revision (published)