尺取法定义（基本概述）
尺取法： 顾名思义，像尺子一样取一段，借用挑战书上面的话说，尺取法通常是对数组保存一对下标，即所选取的区间的左右端点，然后根据实际情况不断地推进区间左右端点以得出答案。尺取法比直接暴力枚举区间效率高很多，尤其是数据量大的时候，所以说尺取法是一种高效的枚举区间的方法，是一种技巧，一般用于求取有一定限制的区间个数或最短的区间等等。当然任何技巧都存在其不足的地方，有些情况下尺取法不可行，无法得出正确答案，所以要先判断是否可以使用尺取法再进行计算。
使用尺取法时应清楚以下四点：
1、 什么情况下能使用尺取法? 2、何时推进区间的端点？ 3、如何推进区间的端点？ 4、何时结束区间的枚举？
尺取法通常适用于选取区间有一定规律，或者说所选取的区间有一定的变化趋势的情况，通俗地说，在对所选取区间进行判断之后，我们可以明确如何进一步有方向地推进区间端点以求解满足条件的区间，如果已经判断了目前所选取的区间，但却无法确定所要求解的区间如何进一步得到根据其端点得到，那么尺取法便是不可行的。首先，明确题目所需要求解的量之后，区间左右端点一般从最整个数组的起点开始，之后判断区间是否符合条件在根据实际情况变化区间的端点求解答案。
例题：
给定一个序列，找出最短的子序列长度，使得其和大于或等于S。
分析：
首先，序列都是正数，如果一个区间其和大于等于S了，那么不需要在向后推进右端点了，因为其和也肯定大于等于S但长度更长，所以，当区间和小于S时右端点向右移动，和大于等于S时，左端点向右移动以进一步找到最短的区间，如果右端点移动到区间末尾其和还不大于等于S，结束区间的枚举。
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <map>
#include <string>
#include <vector>
using namespace std ;
int t,n,k;
const int inf=100000000;
typedef long long ll;
vector<ll> vi;
int main(){
cin>>t;
while(t--){
int ans=inf;
cin>>n>>k;
for(int i=0;i<n;i++){
int num;
cin>>num;
vi.push_back(num);
}
int st=0,en=0,sum=0;//起点和终点
sort(vi.begin(),vi.end());
while(1){
while(en<n && sum<k){
sum+=vi[en++];
}
if(sum<k)break;
ans=min(en-st,ans);//最后的en是多加了1的，所以此处不需要写en-st+1
sum-=vi[st++];//左端点继续右推
}
if(ans==inf)ans=0;
cout<<ans<<endl;
vi.clear();
}
return 0;
}
文章评论