ZYF012 一排奶牛
大约 2 分钟双指针
ZYF012 一排奶牛
【算法标签】 双指针、滑动窗口
【语法标签】 :数组、for循环、while循环、max
题目大意: 在一排数字中,拿掉一些数字,使得连续的相同的数字长度最大。
思路:
枚举没一个数字为要删除的数字,即要剔除的品种
滑动窗口,左指针为第一个不需要移除的数字 a[j] ,依次向右扩展窗口:
- 如果是需要移除的数字,则右指针右移扩展窗口;
- 如果是跟第一个数字
a[j]一样,则右指针右移扩展窗口 且 连续数字计数加1 - 如果右指针不是要移除的数字,也不是
a[j]则打断,不用再继续统计了,因为该数字不能移除,也打断了后续数字跟a[j]继续连续。
#include <bits/stdc++.h>
using namespace std;
const int N = 1e3 + 5;
int a[N];
int main(){
int n;
cin >> n;
for (int i = 0; i < n; i++){
cin >> a[i];
}
// ans 记录找到的最大连续相同奶牛数量
int ans = 0;
// 遍历每头奶牛,将当前奶牛作为要排除的类型 t
for(int i = 0; i < n; i++){
int t = a[i];
// 使用双指针 j 和 k 遍历数组,寻找排除 t 后的最长连续相同奶牛序列
for(int j = 0, k = 0; j < n; ){
// 如果当前奶牛类型等于 t,则跳过
if (t == a[j]){
j++;// 排除掉, 指针右移
continue;
}
// 此时 a[j] != t a[j]为不需要排除的
// k 指向 j 的下一个位置, 开始统计连续相同的奶牛
k = j + 1;
int x = 0;// x 记录连续相同奶牛的数量(不包括第一个)
// 循环查找连续相同的奶牛
while (k < n){
// 如果是 t类型奶牛,跳过
if (a[k] == t){
k++;
continue;
}else if (a[k] == a[j]){// 如果与 a[j] 类型相同,需要排除,计数加 1 并继续查找
x++; // 连续数加1
k++;// 指针右移 扩展窗口
} else {//如果遇到不同类型的奶牛,停止查找
break;
}
}
// 更新 j指针到k位置,继续查找下一段
j = k;
// 更新最大连续相同奶牛数量(X + 1是因为 x 不包括第一个)
ans = max(x + 1, ans);
}
}
cout << ans << endl;
return 0;
}
/*
9
2 7 3 7 7 3 7 5 7
假设需要排除的奶牛为 t = 3;
j = 0时 a[j] = a[0] = 2;
k = j + 1 = 1;
因为 k < n,开始判断
a[k] = a[1] = 7, break;
j = k = 1;
此时 ans = x + 1 = 0 + 1 = 1;
第2轮
j = 1, a[j] = 7 != t
k = j + 1 = 2;
a[k] = a[2] = t; k++;
a[k] = a[3] = 7 ==a[j] x++; 1 k++;4
a[k] = a[4] = 7 == a[j] x++ 2 k++ 5
a[k] = a[5] = 3 == t k++; 6
a[k] = a[6] = 7 == a[j] x++ 3, k++ 7
a[k] = a[7] = 5 break;
此时更新 ans = x + 1 = 4;
*/