尺取法

尺取法

尺取法：顾名思义，像尺子一样取一段，借用挑战书上面的话说，尺取法通常是对数组保存一对下标，即所选取的区间的左右端点，然后根据实际情况不断地推进区间左右端点以得出答案。尺取法比直接暴力枚举区间效率高很多，尤其是数据量大的时候，所以说尺取法是一种高效的枚举区间的方法，是一种技巧，一般用于求取有一定限制的区间个数或最短的区间等等。当然任何技巧都存在其不足的地方，有些情况下尺取法不可行，无法得出正确答案，所以要先判断是否可以使用尺取法再进行计算。

Nowcode

第一次写尺取法的代码，也是第一次接触。

代码语言：javascript复制

#include<iostream>
#include<cstdlib>
#include<string>
#include<algorithm>
using namespace std;
typedef long long ll;
#define INF 0x3f3f3f3f
ll n,k;
 
int main()
{
    cin>>n>>k;
    string s;
    cin>>s;
     
     
    int l,r,ans;
    ans = INF;
    int a[100]={0};
    l = r = 0;
    while(r<s.size())
    {
        a[s[r]-'a']  ;
        while(a[s[r]-'a']>=k)
        {
            ans = min(ans,r-l 1);
             
            a[s[l]-'a']-=1;
            l  ;
        }
        r  ;
    }
    if(ans==INF)   
        cout<<-1<<endl;
    else
        cout<<ans<<endl;
 
    system("pause");
    return 0;
 }

Poj3061

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

代码语言：javascript复制

#include<iostream>
#include<algorithm>
#include<cstring>

using namespace std;
typedef long long ll;
const ll INF = 0x3f3f3f3f;
ll n,m;
ll a[100010];

int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        cin>>n>>m;
        memset(a,0,sizeof(a));
        for(int i =1;i<=n;  i)
            cin>>a[i];
        ll l,r;
        l = 1;
        r = 0;
        ll sum = 0;
        ll ans = INF;
        while(1)
        {
            while(r<=n&&sum<m)  sum =a[  r];
            if(sum<m)   break;
            ans = min(ans,r-l 1);
            sum-=a[l  ];
            
        }
        if(ans==INF)    ans = 0;
        cout<<ans<<endl;
    }
    system("pause");
    return 0;
}

Poj3320

题意：一本书有p页，每一页有一个知识点，知识点可能会重复，求最少连续页数覆盖所有知识点。

代码语言：javascript复制

#include <iostream>
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <map>
using namespace std;
typedef long long LL;
const int N = 1000005;
int a[N];
map<int,int> mp;
int main()
{
    int n;
    while(scanf("%d",&n)!=EOF){
        mp.clear();
        int m=0;
        for(int i=1;i<=n;i  ){
            scanf("%d",&a[i]);
            if(mp[a[i]]==0) m  ;
            mp[a[i]]=1;
        }
        mp.clear();
        int l=1,r=1,cnt=0,ans=n 1;
        while(l<=n){
            while(r<=n&&cnt<m){
                if(mp[a[r]]==0) cnt  ;
                mp[a[r]]  ;
                r  ;
            }
            if(cnt<m) break;
            if(cnt==m) ans = min(ans,r-l);
            mp[a[l]]--;
            if(mp[a[l]]==0) cnt--;
            l  ;
        }
        printf("%dn",ans);
    }
    return 0;
}

技巧

0 人点赞