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

之前的二分答案做法

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

二分查找做法：

我们首先试试只枚举终点。对于终点j，我们的目标是要找到一个让B_j-B_i_-1≥S，且i尽量大（i越大，序列长度j-i+1就越小）的i值，也就是找一个让B_i_-1≤B_j-S最大的i。注意到B是递增的（别忘了，本题中所有A_i均为整数），所以可以用二分查找。（如果不是整数的话可以用之前的二分答案做法）

#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;

		}

}

继续优化：

上面代码的时间复杂度是O(nlogn)。可以将其继续优化到O(n)。由于j是递增的，B_j也是递增的，所以B_i_-1≤B_j-S的右边也是递增的。换句话说，满足条件的i的位置也是递增的。因此我们可以写出这样的程序。

#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;

	}

}

巴特西

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

最新文章

热门文章