常用的解题技巧：尺取法

尺取法：顾名思义，像尺子一样取一段，借用挑战书上面的话说，尺取法通常是对数组保存一对下标，即所选取的区间的左右端点，然后根据实际情况不断地推进区间左右端点以得出答案。之所以需要掌握这个技巧，是因为尺取法比直接暴力枚举区间效率高很多，尤其是数据量大的

时候，所以尺取法是一种高效的枚举区间的方法，一般用于求取有一定限制的区间个数或最短的区间等等。当然任何技巧都存在其不足的地方，有些情况下尺取法不可行，无法得出正确答案。

使用尺取法时应清楚以下四点：

1、  什么情况下能使用尺取法?  2、何时推进区间的端点？ 3、如何推进区间的端点？ 3、何时结束区间的枚举？

尺取法通常适用于选取区间有一定规律，或者说所选取的区间有一定的变化趋势的情况，通俗地说，在对所选取区间进行判断之后，我们可以明确如何进一步有方向地推进区间端点以求解满足条件的区间，如果已经判断了目前所选取的区间，但却无法确定所要求解的区间如何进一步

得到根据其端点得到，那么尺取法便是不可行的。首先，明确题目所需要求解的量之后，区间左右端点一般从最整个数组的起点开始，之后判断区间是否符合条件在根据实际情况变化区间的端点求解答案。

以下是几个经典的使用尺取法的例题，都是从挑战书上引用的。（尺取法通常会需要对某些量进行预处理，以便能在使用时快速地判断。）

总的来说尺取法处理是问题是一段连续的区间，区间是单调的

1、  Poj3061

题意：给定一个序列，找出最短的子序列长度，使得其和大于或等于S。

分析：很明显区间是连续递增的，而且处理的问题也是连续的区间，因此可以用上述方法。我们定义两个指针，头指针和尾指针，开始的时候两个指针都指向数值的开头，然后不断让尾指针增加，判断两个指针的区间和是否大于S， 如果是那么我们就可以固定尾指针，让头指针不断加1直到两段区间和小于S那么首位指针之间的长度+1就是一个以尾指针结尾的最短长度，然后再固定头指针，尾指针+1不断重复上述动作直到数组变量完毕答案就找到了。

时间复杂度$O(N)$

代码：

#include <iostream>
#include <cstring>

using namespace std;

const int N = 100010;
int a[N];

int main()
{
    int T;
    cin >> T;
    while(T --)
    {
        int n, k;
        cin >> n >> k;
        for(int i = 0; i < n; i ++)
            scanf("%d", &a[i]);

        int res = N;// 记录答案
        int sum = 0; // 记录收尾指针区间和
        for(int i = 0, j = 0; i < n; i ++)
        {
            sum += a[i];

            if(sum >= k){
               // 处理区间当这个区间第一次大于等于k的时候我们进行处理，让尾指针固定，头指针++知道区间和小于k, 那么i - j + 2就是这个一尾指针为结尾的区间最小长度，这个时候j的取值就不要动了，可以用来维护下一次区间 的长度
                while(sum >= k)
                {
                    sum -= a[j ++];
                }
                res = min(res, i - j + 2);
            }
        }
        if(res == N)puts("0");
        else
        cout << res << endl;

    }
    return 0;
}

2、  poj3320

题意：一本书有P页，每一页都一个知识点，求去最少的连续页数覆盖所有的知识点。

分析：需要记录的有当前已经覆盖了多少知识点和当前每个知识点覆盖了多少次。很明显本题也是对一段连续的子区间进行处理的，并且也就有单调性，单调递增，因为每次都会新加一个知识点。

时间复杂度$O(N)$

代码：

#include <iostream>
#include <cstring>
#include <map>

using namespace std;
const int N = 1e6 + 10;

int a[N], idx;
int cnt[N];
map<int, int> S;// 本题数据太大需要离散化
int main()
{
    int n;
    scanf("%d", &n);
    for(int i = 0, x; i < n; i ++)
    {
        scanf("%d", &x);
        if(!S.count(x))S[x] = idx ++;
        a[i] = S[x];
    }
    int res = N;
    int sum = 0; // 已经覆盖了多少知识点
    for(int i = 0, j = 0; i < n; i ++)
    {
        if(!cnt[a[i]])sum ++; //如果当前知识没有被覆盖，那么就+1
        cnt[a[i]] ++; //记录每个知识点被覆盖了几次
        if(sum == idx) // 如果sum == idx代表这次刚好完全覆盖所有知识点，因此固定尾指针，移动头指针，知道不完全覆盖知识点，就得到当前最短长度。
        {
            while(-- cnt[a[j ++]]);
            res = min(res, i - j + 2);
            sum --;
        }
    }
    printf("%d\n", res);
    return 0;
}

3、  poj2566

题意：给定一个数组和一个值t，求一个子区间使得其和的绝对值与t的差值最小，如果存在多个，任意解都可行。

思路：n达到了100000，此题就不能用O（n²）枚举区间来做了。考虑连续区间上的xx问题，我们可以用尺取法。可以尺取法要求区间具有单调性，这里有正有负，怎么办？

很简单，我们要求任意区间的和就需要求出前缀数组，然后我们对前缀数组排序就可以了。 排完序后你找的任意两个点都会对应原序列的一个区间（因为会取绝对值，后面减去前面也没关系） 然后用尺取法推进，找出最小的一个即可。

时间复杂度$O(N)$

代码：

#include <iostream>
#include <cstring>
#include <map>
#include <bitset>
#include <algorithm>
#include <cstdio>

using namespace std;
const int N = 1e6 + 10;
bitset<N> f;
typedef pair<int, int> PII;
int a[N], idx;
int cnt[N];
PII s[N];
map<int, int> S;
struct Node
{
    int sub, add, l, r;
};

int main()
{
    int n, m;
    while(cin >> n >> m, n || m)
    {
        s[0].first = 0, s[0].second = 0;
        for(int i = 1; i <= n; i ++)
            scanf("%d", &a[i]), s[i].first = s[i - 1].first + a[i], s[i].second = i;
        sort(s, s + n + 1); // 因为s[0]也算
        while(m --)
        {
            int x;
            int sum = 0;
            Node res;
            res.sub = 2e9;
            scanf("%d", &x);
            int i = 1, j = 0;
            while(i <= n)
            {
                int d = s[i].first - s[j].first; // 每次计算区间和
                if(abs(d - x) < res.sub)
                {
                    //cout << d << endl;
                    res.sub = abs(d - x), res.add = d, res.l = s[i].second, res.r = s[j].second;
                }

                if(d > x)j ++; // 如果大于x的话减小
                else if(d < x)i ++;// 扩大
                else break;// 如果相等就找到最小的
                if(i == j)i ++; //i == j代表区间内没有数，不符合，因此 i ++
            }   
            int l = res.l, r = res.r;
            if(l > r)swap(l, r);// 因为找到的数可能l > r的
            cout << res.add << ' ' << l + 1 << ' ' << r << endl; // 计算的区间是s[r] - s[l] 代表区间l + 1 ,r
        }
    }
    return 0;
}

总结：尺取法的模型便是这样：根据区间的特征交替推进左右端点求解问题，其高效的原因在于避免了大量的无效枚举，其区间枚举都是根据区间特征有方向的枚举，如果胡乱使用尺取法的话会使得枚举量减少，因而很大可能会错误，所以关键的一步是进行问题的分析！