尺取——C语言

尺取

相比于普通的直接暴力枚举，尺取效率就高的多了。
用一个题目来比较一下

如果用通常的方法来解决这个问题就是这样的：

#include<stdio.h>
long long int a[2000010];
int main()
{
    long long int n,m;
    scanf("%lld%lld",&n,&m);
    for(int i=1; i<=n; i++)
        scanf("%lld",&a[i]);
    long long int ans=0,i,j,flag,k;
    while(n--)//一共需要比较的次数
    {
        flag=0;
        j=i;
        k=m;
        while(k--)//m个值相加
        {
            if(j>5)
                j=j%5;//题目说的是一个圈，所以最后会回到第一个
            flag=flag+a[j];//用flag来记住前m个的值
            j++;
        }
        if(flag>ans)//ans就是所要求的最大值，每次拿加好后的flag和ans比较，得到最大的那个
            ans=flag;
        i++;
    }
    printf("%lld",ans);
}

不出所料，提交时间超限，所以现在就要换一种更好的思路，就是用尺取。
尺取呢，大致可以分为两类：
1.固定区间长度的（比如本次的例子）
2.区间长度是不固定的；
这两类都有以下两个方式：
1：一端不动，另一端动；
2：两端同时动（本次例子）；
不多说，康康代码：

#include<stdio.h>
long long int a[2000010];
int main()
{
    long long int n,m;
    scanf("%lld%lld",&n,&m);
    for(int i=1; i<=n; i++)
        scanf("%lld",&a[i]);
    long long int j=1,flag=0,x=m;
    while(x--)//先将前m个加起来，用flag记住，因为后面要用到m，所以我先将m的值赋给x，来控制循环
    {
        flag=flag+a[j];
        j++;
    }
    long long int i=2,ans=0,l=n;//因为后面出现a[i-1]，要减去第一个，所以i从2 开始
    while(l--)
    {
        long long int k=m+i-1;//用k来记录m长度的后一个值
        if(k>n)
        k=k%n;//题目是一个圈，要回到第一个
        flag=flag-a[i-1]+a[k];//更新flag的值:用之前的flag的值减去该m长度的第一个，再加上m长度的后一位
        if(flag>ans)//比较flag与ans的大小，找出符合题意的结果
            ans=flag;
        i++;
    }
    printf("%lld",ans);
}

以上就是我对尺取的理解。