尺取（转）

 

转载自http://blog.chinaunix.net/uid-24922718-id-4848418.html

有这么一类问题，需要在给的一组数据中找到不大于某一个上限的“最优连续子序列”

于是就有了这样一种方法，找这个子序列的过程很像毛毛虫爬行方式比较流行的叫法是“尺取法”。

 

Poj3061

给长度为n的数组和一个整数m，求总和不小于m的连续子序列的最小长度

输入

n = 10，m = 15

5 1 3 5 10 7 4 9 2 8

输出

2

那么我们先用sum存当前这个子序列的和，从左边第一个数来存，直到这个子序列的和大于等于m为止，再记录下当前长度。

其实相当于当不满足条件就入队，然后得到队列长度，再将队首元素出队，再进行下一次的入队，直到满足条件再次出队，并且将这一次的长度与历史最短长度进行取舍，最后扫到最后的元素却无法再满足入队条件的时候就结束，此时用O(n)的时间就可以得到答案。

如下，我把样例用毛毛虫爬一遍，红色的是当前“毛毛虫着地”也就是刚好满足题意的子序列的地方：

//代码如下
 
#include<stdio.h>
int MIN(int x,int y)
{
	return x>y?y:x;
}
int main()
{
	int n,mmax,ans,i,j,sum,m,a[10000];
	scanf("%d",&m);
	while(m--)
	{
		
		scanf("%d%d",&n,&mmax);
	
		for(i=0;i<n;i++)
		scanf("%d",&a[i]);
	
		ans=n+1; //步数
		i=0;
		j=0;
		sum=0; 
	
		while(1)
		{
			while(j<n&&sum<=mmax)  //满足条件一直sum+
			sum+=a[j++];
	
			if(sum<mmax)break; //证明j>n 但是 sum<mmax -->没有满足条件的长度
			ans=MIN(j-i,ans);  //满足条件，ans-->步数的最小值
			sum-=a[i++];   //类似于出队
		}
	
		if(ans>n)
		ans=0;
	
		printf("%d\n",ans);
	
		
	}
	
	
	
}