题目描述
Farmer John 最近购入了N头新的奶牛,每头奶牛的品种是更赛牛(Guernsey)或荷斯坦牛(Holstein)之一。
奶牛目前排成一排,Farmer John 想要为每个连续不少于三头奶牛的序列拍摄一张照片。
然而,他不想拍摄这样的照片,其中只有一头牛的品种是更赛牛,或者只有一头牛的品种是荷斯坦牛——他认为这头奇特的牛会感到孤立和不自然。
在为每个连续不少于三头奶牛的序列拍摄了一张照片后,他把所有「孤独的」照片,即其中只有一头更赛牛或荷斯坦奶牛的照片,都扔掉了。
给定奶牛的排列方式,请帮助 Farmer John 求出他会扔掉多少张孤独的照片。
如果两张照片以不同位置的奶牛开始或结束,则认为它们是不同的。
输入格式
输入的第一行包含N。
输入的第二行包含一个长为N的字符串。如果队伍中的第 i头奶牛是更赛牛,则字符串的第i个字符为G。否则,第i头奶牛是荷斯坦牛,该字符为 H。
输出格式
输出会扔掉的孤独的照片数量。
样例
输入
5
GHGHG
输出
3
样例解释
这个例子中的每一个长为3的子串均恰好包含一头更赛牛或荷斯坦牛——所以这些子串表示孤独的照片,并会被 Farmer John 扔掉。
所有更长的子串(GHGH、HGHG 和 GHGHG)都可以被接受。
算法1
(暴力枚举) $O(n^2)$
会超时的,不写。
算法2
考虑其中的一头牛
假设这头牛为G,我们可以通过遍历统计它左边和右边H牛的数量。
假设左边有L头H牛,右边有R头H牛,当L和R均不为0时,那就会有L*H种孤独的照片。
但是当L为0时,有max(R-1, 0)种;当R为0时,有max(L-1, 0)种。
将这些情况都加在一起。
时间复杂度 $O(n)$
C++ 代码
#include <iostream>
using namespace std;
#include<cmath>
#include<string>
#include<algorithm>
#define N 500005
int L[N], R[N];
int main() {
int n = 0;
string s;
cin>>n;
cin>>s;
long num = 0; //统计孤独的照片
int num_H = 0; //统计H牛数量
int num_G = 0; //统计G牛数量
for(int i=0; i<s.size(); i++){ // 先统计每头牛左边有多少和它品种不同的牛
if(s[i] == 'H'){
L[i] = num_G;
num_G = 0;
num_H++;
}
else{
L[i] = num_H;
num_H = 0;
num_G++;
}
}
num_H = 0;
num_G = 0;
for(int i=s.size()-1; i>=0; i--){ // 再统计每头牛右边有多少和它品种不同的牛
if(s[i] == 'H'){
R[i] = num_G;
num_G = 0;
num_H++;
}
else{
R[i] = num_H;
num_H = 0;
num_G++;
}
}
for(int i=0; i<s.size(); i++){
num += (long)L[i]*R[i] + max(L[i]-1, 0) + max(R[i]-1,0);
}
cout<<num;
}