
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N = 1e6 + 9;
char s[N];
int main()
{
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
 
	cin >> s + 1;
	int n = strlen(s + 1);
	int l = 1, r = n;
	bool ans = true;
	while (l < r&& ans)
	{
		if (s[l] != s[r])ans = false;
		l++, r--;
	}
 
	cout << (ans ? "Y" : "N") << endl;
 
	return 0;
}

快慢指针

快慢指针一般比对撞指针更难想也更难写

指的是两个指针从同一侧开始遍历序列，且移动的步长一个快一个慢。

移动快的指针被称为快指针，移动慢的指针被称为慢指针。

为了方便理解，我们成快指针为r，慢指针为1，这样慢指针和快指针构成区间[1,r]。

两个指针以不同速度、不同策略移动，直到快指针移动到数组尾端，或者两指针相交，或老满足其他特殊条件时为止。

求解步骤

1、使用两个指针l、r。l一般指向序列的第一个元素，即：l=1，r一般指向序列第零个元素，即：r=0.即初始时区间[1,r] = [1,0]表示空区间

2、在循环体中将左右指针向右移动。当满足一定条件时，将慢指针右移，即l++。当满足另外一定条件时（也可能不需要满足条件），将指针右移，即r++，保持[l,r]为合法区间。

3、到指针移动到数组尾端时（即l==n且r==n），或者两指针相交，或者满足其他特殊条件时跳出循环体。

例题蓝桥oj1372美丽的区间

题目描述

给定一个长度为 nn 的序列 a1,a2,⋯ ,ana1,a2,⋯,an 和一个常数 SS。

对于一个连续区间如果它的区间和大于或等于 SS，则称它为美丽的区间。

对于一个美丽的区间，如果其区间长度越短，它就越美丽。

请你从序列中找出最美丽的区间。

输入描述

第一行包含两个整数 n,Sn,S，其含义如题所述。

接下来一行包含 nn 个整数，分别表示 a1,a2,⋯ ,ana1,a2,⋯,an。

10≤N≤10510≤N≤105，1×ai≤1041×ai≤104，1≤S≤1081≤S≤108。

输出描述

输出共一行，包含一个整数，表示最美丽的区间的长度。

若不存在任何美丽的区间，则输出 00。

输入输出样例

示例 1

输入


5 6
1 2 3 4 5

输出

运行限制

最大运行时间：1s
最大运行内存: 128M

解


#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
 
const int N = 1e5 + 9;
int a[N], S;
 
int main()
{
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	int n, S; cin >> n >> S;
 
	int ans = n + 1;
	for (int i = 1; i <= n; i++)cin >> a[i];
 
	for (int i = 1,j = 0,sum = 0; i <= n; i++)
	{
		//考虑移动j，即j++   because i>j说明区间不合法
		while (i > j || (j + 1 <= n && sum < S))sum += a[++j];
 
		if (sum >= S)ans = min(ans, j - i + 1);
		sum -= a[i];
	}
	cout << (ans>n?0:ans) << endl;
	
	return 0;
}

例题蓝桥oj 1621挑选字串

题目描述

有 n 个数，和一个整数 m。

现要从这 n 个数选出一个连续子串，要求这个字串里面至少有 k 个数要大于等于 m。

问一共能选出多少个子串（显然子串长度要大于等于 k）。

输入描述

输入第一行是 3 个整数 n、m、k。

输入第二行是 n 个整数 a1、a2、⋯、an表示序列。

2≤n≤2000，1≤k≤n2，1≤m,ai≤109 2≤n≤2000，1≤k≤2n，1≤m,ai≤109。

输出描述

输出一个整数表示答案。

输入输出样例

示例

输入


7 4 2
4 2 7 7 6 5 1

输出

运行限制

最大运行时间：1s
最大运行内存: 256M

解


#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
 
const int N = 2e5+5;
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, count = 0; i <= n; i++)
	{
		while (i > j || (j + 1 <= n && count < k))//j在i的左边或者>=m的数量小于k
		{
			j++;
			count += (a[j] >= m);
		}
		if (count >= k)ans += (n - j + 1);
		count -= (a[i] >= m);
 
	}
	cout << ans << endl;
	return 0;
}

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/Monodyee/article/detail/628790

c++算法之双指针_c++ 双指针

双指针简介

对撞指针

求解步骤

例题 蓝桥oj1371回文判定

题目描述

输入描述

输出描述

输入输出样例

示例 1

示例 2

运行限制

解

快慢指针

求解步骤

例题 蓝桥oj1372美丽的区间

题目描述

输入描述

输出描述

输入输出样例

示例 1

运行限制

解

例题 蓝桥oj 1621挑选字串

题目描述

输入描述

输出描述

输入输出样例

示例

运行限制

解

例题蓝桥oj1371回文判定

例题蓝桥oj1372美丽的区间

例题蓝桥oj 1621挑选字串