蓝桥杯省赛无忧 第二章 基础算法 课件30 双指针

01 双指针简介

02 对撞指针

#include<iostream>
using namespace std;
int main() {
    
    string str;
    cin >> str;
    
    for (int i = 0, j = str.length() - 1; i < str.length() / 2; i ++, j --) {
        
        if (str[i] != str[j]) {
            cout << "N";
            return 0;
        }
        
    }
    cout << "Y";
    return 0;
}

03 快慢指针

#include<iostream>
using namespace std;
int n,k,a[100005];
int main()
{cin>>n>>k;
for(int i=1;i<=n;i++)
cin>>a[i];
int sum=0,ans=1e9;
for(int i=1,j=0;i<=n;i++)
{ while(sum<k&&j<=n)
  j++,sum+=a[j];
  if(sum>=k)
  ans=min(ans,j-i+1);
  sum-=a[i];
}
if(ans==1e9)
cout<<0;
else
cout<<ans;
}

#include <bits/stdc++.h>
using namespace std;
const int N=2000;
int a[N];
int main()
{
  ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
  int n,m,k;
  cin>>n>>m>>k;
  for(int i=1;i<=n;i++)
  {
    cin>>a[i];
  }
  int ans=0;
  for(int i=1,j=0,cnt=0;i<=n;i++)
  {
    while(i>j||(j+1<=n&&cnt<k))
    {
      cnt+=(a[++j]>=m);
    }
    if(cnt>=k)
    ans+=n-j+1;
  cnt-=(a[i]>=m);
  }
  cout<<ans<<endl;
  return 0;
}