尺取法：尺取法是一种比较基础的算法,一般用来解决具有单调性的区间问题。尺取法通常是根据实际情况不断地推进区间左右端点以得出答案。尺取法比直接暴力枚举区间效率高很多，尤其是数据量大的时候，所以说尺取法是一种高效的枚举区间的方法，是一种技巧，一般用于求取有一定限制的区间个数或最短的区间等等。
使用尺取法时应注意以下几点：① 尺取法的应用范围？ ② 区间的端点合适以及如何推进？ ③ 何时结束区间的枚举?
尺取动作??
#include<iostream>
#include<algorithm>
#include<cstdio>
using namespace std;
const int maxn=100005;
int w[maxn];
int main()
{
int T,j,i,n,S,ans,sum;
scanf("%d",&T);
while(T--)
{
ans=maxn;sum=0;j=1;
scanf("%d%d",&n,&S);
for(i=1;i<=n;i++) scanf("%d",&w[i]);
for(i=1;i<=n;i++)
{
sum+=w[i];
while(sum>=S)
{
ans=min(ans,i-j+1);
sum-=w[j];
j++;
}
}
printf("%d\n",ans==maxn?0:ans);
}
return 0;
}
poj 3320 Jessica‘s Reading Problem
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<set>
#include<map>
using namespace std;
const int maxn=1000005;
int w[maxn],P;
set<int> seti;
map<int,int> imapi;
int main()
{
int i,j=0,sum=0,ans=maxn;
scanf("%d",&P);
for(i=0;i<P;i++)
{
scanf("%d",&w[i]);
seti.insert(w[i]);
}
for(i=0;i<P;i++)
{
if(++imapi[w[i]]==1) sum++;
while(sum==seti.size())
{
ans=min(ans,i-j+1);
if(--imapi[w[j]]==0) sum--;
j++;
}
}
printf("%d\n",ans);
system("pause");
return 0;
}
poj 2739 Sum of Consecutive Prime Numbers
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<vector>
using namespace std;
const int maxn=10005;
int flag[maxn]={1,1,0};
vector<int> prime;
void init();
int main()
{
init();
int n,i,j,ans,sum;
while(~scanf("%d",&n)&&n)
{
i=j=sum=ans=0;
for(i=0;i<prime.size();i++)
{
sum+=prime[i];
while(sum>n)
{
sum-=prime[j];
j++;
}
if(sum==n) ans++;
}
printf("%d\n",ans);
}
return 0;
}
void init()
{
int i,j;
for(i=2;i<=maxn;i++)
{
if(flag[i]) continue;
else
{
prime.push_back(i);
for(j=2*i;j<=maxn;j+=i)
flag[j]=1;
}
}
}
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<vector>
#include<cmath>
using namespace std;
const int maxn=2000;
long long L[maxn],R[maxn],cnt;
int main()
{
long long i,j,n,sum=0;
scanf("%lld",&n);
for(i=j=1;i<=sqrt(n);i++)
{
sum+=i*i;
while(sum>n)
{
sum-=j*j;
j++;
}
if(sum==n)
{
L[cnt]=j;
R[cnt++]=i;
}
}
printf("%d\n",cnt);
for(i=0;i<cnt;i++)
{
printf("%lld",R[i]-L[i]+1);
for(j=L[i];j<=R[i];j++) printf(" %lld",j);
printf("\n");
}
return 0;
}
原文：https://www.cnblogs.com/VividBinGo/p/11370269.html