﻿ 【二分查找+优化O（n）】【续UVA1121】Subsequence

### 【二分查找+优化O（n）】【续UVA1121】Subsequence

http://blog.csdn.net/zy691357966/article/details/40212215

```#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <ctime>
#include <algorithm>
#include <iostream>
#include <sstream>
#include <string>
#define oo 0x13131313
#define maxn 100000+100
using namespace std;
int n,S;
int A[maxn];
int ans;
void input()
{
ans=oo;
for(int i=1;i<=n;i++)
{
scanf("%d",&A[i]);
A[i]+=A[i-1];
}
}
int find(int n)
{
int s=1,e=n,m=0;
if(A[n]-A[s-1]<S) return -1;
while(s<e)
{
m=(s+e)/2+1;
if(A[n]-A[m-1]>=S)
s=m;
else
e=m-1;
}
return s;
}
int main()
{
//	freopen("a.in","r",stdin);
//	freopen("a.out","w",stdout);
int k;
while(cin>>n>>S)
{
input();
for(int i=1;i<=n;i++)
{
k=find(i);
if(k!=-1)
{
ans=min(ans,i-k+1);
}
}
if(ans==oo)
ans=0;
cout<<ans<<endl;
}
}
```

```#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <ctime>
#include <algorithm>
#include <iostream>
#include <sstream>
#include <string>
#define oo 0x13131313
#define maxn 100000+100
using namespace std;
int n,S;
int A[maxn];
int ans;
void input()
{
ans=oo;
for(int i=1;i<=n;i++)
{
scanf("%d",&A[i]);
A[i]+=A[i-1];
}
}
int main()
{
freopen("a.in","r",stdin);
freopen("a.out","w",stdout);
while(cin>>n>>S)
{
int i=1;
input();
for(int j=1;j<=n;j++)
{
if(A[j]-A[i-1]>=S)
{
while(A[j]-A[i-1]>=S&&i<=j)
{
ans=min(ans,j-i+1);
i++;
}
}
}
if(ans==oo) ans=0;
cout<<ans<<endl;
}
}
```