常用技巧精选

概述

本文所涉及的多种技巧，出自秋叶拓哉的《挑战程序设计》一书。译者提及这些技巧的应用范围都比书中所介绍的模型要广泛，我们应该注重算法技巧中蕴含的算法思想以及思维方式。许多看似复杂困难的问题，关键都可以运用看似简单的技巧处理。我查询网上对于这些技巧的解释，希望能够深化这种技巧蕴含的思想，并且将其变为自己的东西。

技巧精选

尺取法

概述

尺取法通常是指对数组保存一对下标（起点，终点），然后根据实际情况交替推进两个端点知道得出答案的方法，这种操作很像是尺蠖（日文中称为尺取虫）爬行的方式故得名（这是书中译者注释）。

思想

说到底，尺取法只是一种模拟方法，通过模拟尺取虫的前进方式不断移动所选区间，验证区间内元素和题目所给条件是否符合。一般是在给的一组数据中找到不大于某一个上限的“最优连续子序列” 。而通过这种方法，能够将这一类问题的时间复杂度降低。

那么什么时候能够使用尺取法呢，不能使用尺取法的题目贸然使用一定会导致错误答案或者其他错误。

尺取法通常适用于我们所要选取的区间有明显的变化趋势的题目。换句话说，我们需要知道这次变动之后，下一步所选区间变化的方向或者形式。一般确定了可以应用尺取法之后，所取区间的左右端点都应从数组左端开始选取。

假如给你一些数，需要在这些数中找到一个区间，使得区间里每一个元素的和大于或等于给定的某个值。若不用尺取法，我们需要对于每一个区间的起始点，枚举终点，加和起点与终点之间的元素。这个过程需要开二重循环，就算有所剪枝，时间复杂度也是在O(n^2)左右。在这个过程中，我们很明显可以发现区间中元素的加和出现了重复累赘的地方，这些加和的过程和剪枝的过程叠加在一起就得到了尺取法的初始模型。

以上题为例，当我们现在所选区间的和不足给定的值，则区间的终点右移，区间和加上刚进入区间的点的值。而当我们现在所选区间和超过了给定的值，则区间起点右移，区间和减去刚出区间的点的值。这样我们可以得到每一个满足条件的区间。很明显可得，运用尺取法的思想，时间复杂度变成了O(n)。

例题

POJ 3061 Subsequence

这道题是《挑战程序设计》书中第一道例题，大意就是求总长不小于S的连续子序列的长度的最小值，若解不存在，则输出0。

题目

http://poj.org/problem?id=3061

思路

书中提及，本题可以用前缀和加二分法将O(n^2)的时间复杂度缩减至O(nlogn)。首先前缀和可以让查询区间和的时间复杂度变成O(1)，然后我们确定区间的起点，通过二分法枚举区间终点，最终复杂度变成O(nlogn)。

这时我们开始讲解尺取法的该题解题思路，假设以a[s]开始总和最初大于S时的连续子序列为a[s]+a[s+1]+…+a[t-1]。此时，a[s+1]+…+a[t-2]<a[s]+…+a[t-2]<S。所以从a[s+1]开始总和最初超过S的连续子序列如果是a[s+1]+…+a[t’-1]的话，则必然有t<=t’。

利用这个特性，我们可以得出只要当前区间和小于S，就把区间终点右移的思路，而区间和大于等于S的时候，就把区间起点右移。

通过这样一个模拟的过程，我们可以很轻松得出最小长度。

代码

#include<stdio.h>
int main()
{
    int n;
    int lo,s;
    int a[100005];
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d%d",&lo,&s);
        for(int j=1;j<=lo;j++)
        {
            scanf("%d",&a[j]);
        }
        int l=1,r=1,sum=a[1],min=100005;
        while(1)
        {
            if(sum<s&&r<lo)
            {
                r++;
                sum+=a[r];
            }
            else if(sum>=s)
            {
                    if(r-l+1<min)
                {
                    min=r-l+1;
                }
                sum-=a[l];
                l++;
            }
                else if(sum<s&&r>=lo)
                {
                    break;
            }
        }
        if(min==100005)
        {
            printf("0\n");
        }
        else
        {
            printf("%d\n",min);			
        }
    }
    return 0;
}

反转（开关问题）

未完待续……