【尺取法】Subsequence

74 阅读 0 评论 49 点赞

我是靠谱客的博主拉长唇膏，这篇文章主要介绍【尺取法】Subsequence，现在分享给大家，希望可以做个参考。

3061 -- Subsequence (poj.org)

题意：

给定一个序列，让你求超过k的最短子串的长度

思路：

标准尺取法模板，剪枝了很多不符合条件的情况，复杂度为O(n)

按原理来说：

如果让我们去求长度超过k的所有子串中最短的长度，首先第一个想法是不是枚举。考虑枚举每一个子串，如果满足条件就去统计最短子串的长度。但是这样效率很低，因为在状态空间中存在很多无效的状态，即这些状态不满足子串和超过k的条件。

因为我们要求的是最短长度，因此只需要枚举子串和刚好超过k的子串就好了。

如何去枚举，按左指针 l 分类，即将所有状态按左指针去划分状态

对于每个左指针，去找到第一个子串和超过k的区间就行。在r++的过程中直接就省略了不满足条件的子串

找到之后，l++，换一个种类去枚举，因此ans-=s[l]

下一轮的新子串不满足条件，但是它是以新的 l 为起点的最接近条件的子串，因此也省去枚举以新的 l 为起点的很多状态

尺取法一般去解决区间权值满足单调性的问题，即区间权值的大小和区间长度要不单调递增，要不单调递减，这样就保证了在枚举新的 l 时，得到的区间是最接近满足条件的区间

Code：

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include <stdio.h>
#define min(a,b) (a<b?a:b)
using namespace std;
const int mxn=1e6+10,mnf=0x3f3f3f3f;
#define int long long
int n,s,r,sum=0,ans=mnf,res=0;
int a[mxn];
void solve(){
ans=mnf;sum=0;res=0;
scanf("%lld%lld",&n,&s);
for(int i=1;i<=n;i++) scanf("%lld",&a[i]),res+=a[i];
if(res<s){
puts("0");
return;
}
r=0;
for(int l=1;l<=n;l++){
while(r<n&&sum<s){
r++;
sum+=a[r];
}
if(sum>=s&&r-l+1<=n){
ans=min(ans,r-l+1);
}
sum-=a[l];
}
printf("%lldn",ans);
}
signed main(){
int T;
scanf("%lld",&T);
while(T--)solve();
return 0;
}