Fork me on GitHub

尺取法(双指针)训练

个人理解是尺取法是用单调性来用双指针优化枚举的一种东西

例题1:

给你一个n和s,然后给出n个数,求这n个数中和大于等于s的最小连续序列。保证所有元素为正

首先暴力肯定就是直接$O(n^2)$枚举,然后我们考虑尺取怎么做,首先我们发现题目中的一个重要条件:所有元素都为正,那么如果一段区间作为另外几段区间的子区间,那么一定包含这个区间的长区间的长度越长,这个区间里的值就越大.所以对于我们枚举的右端点,我们发现如果对于开始的左端点已经包含了$sum$大于$s$的子区间,那么我们用左端点右移来让这个区间长度减小,对应的区间和也会减小,当我们发现左端点已经不能右移(即再移一次就会使得$sum < s$),那么现在的区间即为右端点$r$所对应的最短的和大于等于$s$的区间.

然后我们考虑最终答案一定是某个右端点和某个左端点构成的区间,所以在我们所有最终的区间中一定会包含到答案区间.

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
#include <bits/stdc++.h> 
using namespace std;
const int N=1e5+5;
int n , s , sum , len;
int a[N];
int main(){
int T;
scanf ( "%d" , &T );
while ( T-- ) {
sum=0;
scanf ( "%d%d" , &n , &s );
len=n+1;
for(int i=1;i<=n;i++)
scanf("%d",&a[i]);
int l = 1 , r = 1;
for(;r<=n;r++){
sum+=a[r];
if(sum<s)
continue;
while(sum-a[l]>=s)
sum-=a[l++];
len=min(len,r-l+1);
}
if(len==n+1) printf("%d\n",0);
else printf("%d\n",len);
}
}

例题2:

给你一个数,求这个数能有多少种连续的质数构成。

发现题目可以等价成:给你一个$v$和所有的质数组成的序列,然后求出有多少子区间的和为$v$.

发现求和显然满足单调性的,所以可以直接双指针即可.

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
35
36
37
38
39

#include <bits/stdc++.h>

using namespace std;
const int N=1e4+5;
int su[N],cnt;
bool isprime[N];
void prime(){
cnt=1;
memset(isprime,1,sizeof(isprime));
isprime[0]=isprime[1]=0;
for(int i=2;i<N;i++){
if(isprime[i]) su[cnt++]=i;
for(int j=i*2;j<=N;j+=i)
isprime[j]=0;
}
}

int main(){
prime();
int l,r;
int n;
int sum,num;
while(scanf("%d",&n)!=-1){
if(n==0) break;
sum=0;
num=0;
for(l=1,r=1;r<=n;r++){
sum+=su[r];
if(sum<n) continue;
if(sum==n) num++;
while(sum-su[l]>=n){
sum-=su[l++];
if(sum==n) num++;
}
}
printf("%d\n",num);
}
}

例3:

题目连接

这道题如果我们按照纯粹的暴力的思想的话我们会先暴力枚举所有的区间,然后再在这个区间中找出一个长度为$d$的权值最大的区间,然后用$sum[r]-sum[l-1]-sum[x]+sum[x-d]$来判断这个区间是否可行然后更新答案.但是这样很显然是$O(n^3)$的,所以需要考虑怎么优化.
我们发现,如果一段区间减去长度为$d$的子区间和一直小于$p$的话,那么这段子区间是可以一直被选择的(注意是可以被选择而不是一定要被选择).所以我们可以对于区间维护一段可以删的区间中的权值和的最大值.
我们记录$t_i$表示在$[i-d+1,i]$这段区间的区间和,然后用双指针枚举区间范围:当$r$可以右移,即当前$l,r$所以应区间和减去这段区间中$t$的最大值小于等于$p$时,就可以一直右移,然后我们用单调队列来维护这些$t$更新答案即可.

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
35
36
37
#include <bits/stdc++.h>
#define int long long
using namespace std;

const int N = 2e6 + 10;

int n , p , d;
int a[N] , sum[N] , t[N];
deque < int > qu;

signed main ( void ) {
scanf ( "%lld%lld%lld" , &n , &p , &d );
for ( int i = 1 ; i <= n ; i++ ) {
scanf ( "%lld" , &a[i] );
sum[i] = sum[i - 1] + a[i];
if ( i >= d )
t[i] = sum[i] - sum[i - d];
else
t[i] = sum[i];
}
int now = sum[d] , ans = -1 , l = 1 , r;
qu.push_back ( d );
for ( r = d + 1 ; r <= n ; r++ ) {
now += a[r];
while ( !qu.empty () && t[qu.back()] <= t[r] )
qu.pop_back ();
qu.push_back ( r );
while ( now - t[qu.front ()] > p ) {
if ( qu.front() < l + d )
qu.pop_front();
now -= a[l++];
}
ans = max ( ans , r - l + 1 );
}
printf ( "%lld\n" , ans );
return 0;
}
因为知道了自己是多么的菜,所以才要更加努力去追求那个永远也不可能实现的梦想

本文标题:尺取法(双指针)训练

文章作者:兮水XiShui丶

发布时间:2021年04月10日 - 10:04

最后更新:2021年04月10日 - 13:04

原始链接:http://krrrr.top/2021/04/10/尺取法-双指针-训练/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。