尺取法
尺取法
尺取法：顾名思义，像尺子一样取一段，借用挑战书上面的话说，尺取法通常是对数组保存一对下标，即所选取的区间的左右端点，然后根据实际情况不断地推进区间左右端点以得出答案。尺取法比直接暴力枚举区间效率高很多，尤其是数据量大的时候，所以说尺取法是一种高效的枚举区间的方法，是一种技巧，一般用于求取有一定限制的区间个数或最短的区间等等。当然任何技巧都存在其不足的地方，有些情况下尺取法不可行，无法得出正确答案，所以要先判断是否可以使用尺取法再进行计算。
Nowcode
第一次写尺取法的代码，也是第一次接触。
#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，求最短的子序列长度。
#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页，每一页有一个知识点，知识点可能会重复，求最少连续页数覆盖所有知识点。
#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("%d\n",ans);
}
return 0;
}本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2020-02-17|，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录
腾讯云开发者
