ACM技巧：尺取法

尺取法通常指的是保存数组的一组下标（起点和终点），然后根据实际情况，交替地推进这两个下标，然后获得结果的方法。

其实就很像毛毛虫在前进的时候蠕动身体的过程。

题目：http://poj.org/problem?id=3061

方法1：先对数组求前缀和sum。然后对于sum数组，从第0位开始一直往右，利用upper_bound，计算出第一个大于sum[i]+S的坐标，然后计算区间长度t-s，利用min(ans, t-s)来更新ans。本方法时间复杂度为O(NlogN)。

方法2：利用“若s~t的a[i]的和刚好满足sum>S，则对于s+1~t’，也刚好满足sum>S的话，需要t’≥t，这一性质。就可以在O(N)的时间内完成求解。

方法1的AC代码：

#include <iostream>
#include <string.h>
#include<algorithm>
using namespace std;

#define MAXN 100005

typedef long long ll;
ll pre[MAXN];
int main()
{
    int t, n;
    ll s;
    int tmp;
    scanf("%d", &t);
    while (t--)
    {
        memset(pre, 0, sizeof(pre));
        scanf("%d%lld", &n, &s);
        for (int i = 1; i <= n; ++i)
        {
            scanf("%d", &tmp);
            pre[i] = pre[i - 1] + tmp;
        }
        //无解
        if(pre[n]<s)
        {
            printf("0\n");
            continue;
        }

        //尺取法
        
        int min_len = MAXN;
        for(int st = 0;pre[st]+s<=pre[n];++st)
        {
            min_len = min(min_len, int(lower_bound(pre+st, pre+n, pre[st]+s)-pre-st));
        }
        
        printf("%d\n", min_len);
    }
}

方法2的AC代码：

#include <iostream>
#include <cstdio>
#include <string.h>
using namespace std;
typedef long long ll;

#define MAXN 100005
int a[MAXN];
int t, n;
ll s;
int main()
{
    scanf("%d", &t);
    while (t--)
    {
        scanf("%d%lld", &n, &s);
        memset(a, 0, sizeof(a));

        for (int i = 0; i < n; ++i)
        {
            scanf("%d", &a[i]);
        }

        int st = 0, to = 0;
        ll sum = 0;
        int ans = (1 << 30);

        while (1)
        {
            while (sum < s && to < n)
            {
                sum += a[to];
                ++to;
            }

            if (sum < s)
                break;
            ans = min(ans, to - st);
            sum -= a[st];
            ++st;
        }

        if (ans > n)
        {
            ans = 0;
        }

        printf("%d\n", ans);
    }
}

题目：http://poj.org/problem?id=3320

这题的思路和上题的方法2相似，在某个区间[s,t]已经覆盖了所有知识点的情况下，这时去除区间头，然后继续寻找下一个结果。

AC代码：

#include <map>
#include <iostream>
#include <algorithm>
#include <set>
using namespace std;

typedef long long ll;

#define MAXN 1000006

int a[MAXN];
int p;
int main()
{
    scanf("%d", &p);
    set<int> tmp_set;
    for (int i = 0; i < p; ++i)
    {
        scanf("%d", &a[i]);
        tmp_set.insert(a[i]);
    }

    int st = 0, to = 0;

    map<int, int> mp;

    int ans = MAXN;
    int kinds = tmp_set.size();
    int current_kinds = 0;
    while (1)
    {
        while (to < p && current_kinds < kinds)
        {
            if (mp[a[to]] == 0)
            {
                //出现新的知识点
                mp[a[to]] = 1;
                ++current_kinds;
            }
            else
                ++mp[a[to]];
            ++to;
        }
        if (current_kinds < kinds)
            break;

        ans = min(ans, to - st);

        mp[a[st]]--;
        if (mp[a[st]] == 0)
            --current_kinds;
        ++st;
    }
    printf("%d\n", ans);
}

转载请注明来源：https://www.longjin666.top/?p=1189

欢迎关注我的公众号“灯珑”，让我们一起了解更多的事物~