POJ 3061 Subsequence 二分或者尺取法

题目大意：

给定长度为n的整列整数a[0],a[1],……a[n-1]，以及整数S，求出总和不小于S的连续子序列的长度的最小值。

思路:

方法一：

首先求出各项的和sum[i]，这样可以在O(1)的时间内算出区间上的总和，这样，枚举每一个起点i，然后二分搜索出结果大于sum[i]+tot的最小下标。（tot是题目中的S）

总的时间为O(nlogn）

方法二：

设以a[s]开始的总和最初大于S时的连续子序列为a[s]+a[s+1]+……a[t-1]，这时，a[s+1]+a[s+1]+……a[t-2]<a[s]+a[s+1]+……a[t-2]<S,所以如果从a[s+1]开始总和最初超过S的连续子序列是a[s+1]+……a[t‘-1]，则t<=t'。

故可以设计如下算法：

1.初始s=t=sum=0

2.只要依然有sum<S,就不断将sum加上a[t],并且t=t+1；

3.如果2中无法满足sum>=s则终止，否则ans=min(ans,t-s);

4.将sum减去a[s],s+=1后回到2

总复杂度为O(N)

1.二分法

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

const int MAXN=100000+10;

const int INF=0x7fffffff;

int a[MAXN],sum[MAXN];

int search(int L,int R,int target) //(L,R]

{

	while(L<R-1)

	{

		int m=(L+R)>>1;

		if(sum[m]<target)

			L=m;

		else

			R=m;

	}

	return R;

}

int main()

{

	int T;

	scanf("%d",&T);

	while(T--)

	{

		int n,tot;

		scanf("%d%d",&n,&tot);

		sum[0]=0;

		for(int i=1;i<=n;i++)

		{

			scanf("%d",&a[i]);

			sum[i]=sum[i-1]+a[i];

		}

		int ans=INF;

		for(int i=1;i<=n&&sum[i]+tot<=sum[n];i++)

		{

			int t=search(i,n,tot+sum[i]);//sum[t]-sum[i]>=tot -> sum[t]>=tot+sum[i]

			ans=min(ans,t-i);

		}

		if(ans==INF)

			printf("0\n");

		else

			printf("%d\n",ans);

	}

	return 0;

}

2.尺取法

#include<cstdio>

#include<algorithm>

using namespace std;

const int MAXN=100000+10;

const int INF=0x7fffffff;

int a[MAXN];

int main()

{

	int T;

	scanf("%d",&T);

	while(T--)

	{

		int n,tot;

		scanf("%d%d",&n,&tot);

		for(int i=0;i<n;i++)

			scanf("%d",&a[i]);

		int s=0,t=0,sum=0,ans=INF;

		while(true)

		{

			while(sum<tot && t<n)

			{

				sum+=a[t++];

			}

			if(sum<tot) break;

			ans=min(ans,t-s);

			sum-=a[s++];

		}

		if(ans==INF)

			printf("0\n");

		else

			printf("%d\n",ans);

	}

	return 0;

}

巴特西

POJ 3061 Subsequence 二分或者尺取法

最新文章

热门文章