现在的位置: 首页 > 综合 > 正文

常用技巧之 尺取法 【 理解 + 例题 】

2019年02月19日 ⁄ 综合 ⁄ 共 2358字 ⁄ 字号 评论关闭

    尺取法的复杂度为 O(n) ,主要应用有关连续性的问题,基本原理就是反复地推进区间的开头和末尾,来求取满足条件的最小区间,或者相似的应用。

    尺取法在别的地方又被称为滑动窗口或者蠕虫算法,我觉得蠕虫算法这个名称用的相当恰当啊,就是一步一步地往后移动,一直找到答案,而不用遍历回溯什么的,也就是因为这样,他的复杂度才这么低。

    举例子什么的,就直接看题目好了,搞了三个例题,看完应该会有一定的理解了吧。

   
NBUT 1052  想减肥的字符串  

    该题就是让你求最短的,同时包含a b c 的字符串的长度,数据较水,好像遍历,DP 也可以过,这题用尺取法的话,时间是0 ms,也就是说还是很高效的。

  

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

char tt[1010];
int cnt[200];

int main()
{
    while(~scanf("%s",tt))
    {
        int len = strlen(tt);
        int sta = -1, ans = len;
        for(int i = 0; i < len; i ++)
        {
            while( (!cnt['a'] || !cnt['b'] || !cnt['c']) && sta < len - 1)
            {
                sta ++;
                cnt[tt[sta]] ++;
            }
            if(cnt['a'] && cnt['b'] && cnt['c'])
                ans = min(sta - i + 1, ans);
            cnt[tt[i]] --;
        }
        printf("%d\n", ans);
    }
}

    POJ  3061  Subsequence

   该题就是给你长度为n的整列整数a[0],a[1],……a[n-1],以及整数S,求出总和不小于S的连续子序列的长度的最小值。

   你只要不断的把下标往前“ 蠕动 ” 就可以了,比如a[0],a[1]....a[k],然后a[1],a[2]....a[k],a [k+1] , 一直持续着,中间可能有多种满足状况,你要找出最短的长度即可

 

#include<stdio.h>
#include<algorithm>
#include<cstring>
#include<queue>
#include<cmath>
using namespace std;

const int INF = 0x7fffffff;
int tt[100010];
int t, n, tot;

int main()
{
    while(~scanf("%d",&t))
    {
        while(t --)
        {
            scanf("%d %d",&n, &tot);
            for(int i = 0;i < n; i ++)
                scanf("%d",&tt[i]);
            int sta = 0, endd = 0;               //  sta 到 endd 为一个区间 ,sta不断向前蠕动....
            int sum = 0, ans = INF;
            while(1)
            {
                while(sum < tot && endd < n)
                {
                    sum += tt[endd ++];
                }
                if(sum < tot)
                    break;
                ans = min(ans, endd - sta);
                sum -= tt[sta ++];
            }
            if(ans == INF)
                printf("0\n");
            else
                printf("%d\n",ans);
        }
    }
    return 0;
}

   
NBUT   1576   炒鸡想减肥的字符串

      该题感觉稍微复杂一点,但是和第一题几乎一模一样,要注意的是,但m 为3 的时候,就不能考虑d, e , f, 什么的,这题题意我看错了三次,还好最后还是一A,直接上代码了(该解法还是RANK 的第一   其它的解法好像也有0ms 的,  大神请一定分享一下啊 ,在下感激不尽)  好吧,其实你会发现judge 的两个函数一样的,cnt 和nut的重复,自己再改一下好了,这是比赛的代码知己贴上去了- 。 -

#include<stdio.h>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<queue>
using namespace std;

const int N = 100010;
char tt[1010];
int cnt[1110];  // 看是否出现过该字符
int nut[1110];
int t, a, b;

int num;

int judge()
{
    for(int i = 0; i < b; i ++)
    {
        if(!cnt['a' + i])
            return 1;
    }
        return 0;
}
int judge1()
{
    for(int i = 0; i < b; i ++)
    {
        if(!nut['a' + i])
            return 1;
    }
        return 0;
}

int main()
{
    while(~scanf("%d",&t))
    {
        while(t --)
        {
            memset(cnt, 0, sizeof(cnt));
            memset(nut, 0, sizeof(nut));
            scanf("%d%d",&a,&b);
            scanf("%s",tt);
            int sta = -1, ans = a;
            for(int i = 0; i < a; i ++)
            {
               // num = 0;
                while(judge() == 1 && sta < a)
                {
                        sta ++;
                    cnt[tt[sta]] ++;
                    nut[tt[sta]] ++;
                   // printf("AA  %d %c %d %d \n", sta, tt[sta], num , b);
                   // num = 0;
                }
                if(judge() == 0)
                    ans = min(sta - i + 1, ans);
                cnt[tt[i]] --;
               // printf("%d %d %d\n",sta, i, ans);
            }
            if(judge1() == 0 || ans < a)
                printf("%d\n",ans);
            else
                printf("I am so fat!\n");
        }
    }
    return 0;
}

 -------------------------------------------  渣渣的算法路 , 大神勿喷, 欢迎一起交流 , 有事请留言
 

抱歉!评论已关闭.