尺取

尺取

1.简单介绍：

尺取法通常是对数组保存一对下标，即所选取的区间的左右端点，然后根据实际情况不断地推进区间左右端点以得出答案。尺取法比直接暴力枚举区间效率高很多，尤其是数据量大的时候，所以说尺取法是一种高效的枚举区间的方法。

而且找这个子序列的过程很像毛毛虫爬行方式，就是从起点开始，不断伸长头部，直到和大等于s，然后收尾部，使和大等于s的情况下数的个数最少。得到一个区间，将区间长度和当前最小值比较并取最小值，然后继续往前爬行找下一个数。。

2.尺取法示意：取得满足条件的最小序列，然后依次将i向右移动，若i向左移动也同样满足条件，则j不动，否则j也向右移动。在移动过程中记录j-i的最小值。

首先i指向5；j指向10的位置；

3.应用

例1：有两个整数n,m,n代表数列长度，

数列的最后一项等于第一项，求连续m序列的最大值。

#include<stdio.h>
long long int a[4000000];//范围很大，定义为全局变量
int main()
{
    int n,m,i;
    long long int sum,max;
    scanf("%d%d",&n,&m);
    sum=0;
    for(i=0;i<n;i++)
    {
        scanf("%lld",&a[i]);
        if(i<m)
        {
            sum+=a[i];
            a[n+i]=a[i];//由于桌子是圆的，所以a[n+i]=a[i].
        }
    }
    max=0;
    for(i=m;i<m+n;i++)
    {
        if(sum>max)
        {
            max=sum;
        }
        sum+=a[i];//每向后面增加一个，前面就减掉一个，有点类似于队列。
        sum-=a[i-m];
    }
    printf("%lld\n",max);
    return 0;
}

例2.有两个整数n,m,n代表数列长度，判断总和不小于m的最大子序列长度

int main()
{
	int n,m,ans,i,j,a[1000],sum;
	scanf("%d%d",&n,&m);
	for(i=0;i<n;i++)
    {
		scanf("%d",&a[i]);
    }
	i=0;
	j=0;
	sum=0;
	ans=n+1;
	while(1)
	{
		while(j<n&&sum<m)
			sum+=a[j++];//扩大右端点
		if(sum<max)	
        break;
		ans=ans<(j-i)?ans:(j-i);//求出j-i最小值与ans比较
		sum-=a[i++];//扩大左端点
	}
	printf("%d\n",ans);
	return 0;
}
 

4.心得：

通过尺取的学习，领会到通过借助身边事物来举例，模拟学习的优势。