2023.2.18 修复代码 bug。
hack 数据:
4
GHHG
4 3 3 4
贪心。能想到的话其实代码很短。
我们可以把选择的两个领导分为两种情况:
-
有一个领导可以管理自己所有种类的牛,且另外一个领导可以管理这个领导。
-
两个领导都可以管理各自种类的牛。
把这个想出来代码也就自然好写了。
我们可以先把两种种类第一次和最后一次出现的牛出现的位置找出来。
之后我们可以看到,如果这头牛能管控的牛可以当领导(那么这个被管控的领导管控的牛必须包括所有和自己种类一样的牛),如果满足,那么就形成一对。
如果两头牛都可以管控所有和自己种类一样的牛,那么也是一对。
注:另外需要注意,如果之前两头牛已经成为一组,则不算。
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+10;
int a[N];
signed main()
{
int n;
cin>>n;
string st;
cin>>st;
st=' '+st;
int g=0,h=0,G=0,H=0;
for(int i=1;i<st.size();i++){
if(st[i]=='G'&&!g)g=i;
else if(st[i]=='H'&&!h)h=i;
}
for(int i=st.size()-1;i>=1;i--){
if(st[i]=='G'&&!G)G=i;
else if(st[i]=='H'&&!H)H=i;
}
for(int i=1;i<=n;i++)cin>>a[i];
char ch;
int ans=0;
bool gg=0,hh=0;
for(int i=1;i<=n;i++){
if(st[i]=='G'){
if(a[i]>=h&&i<=h&&a[h]>=H){
ans++;
if(i==g)gg=1;
}
}
if(st[i]=='H'){
if(a[i]>=g&&i<=g&&a[g]>=G){
ans++;
if(i==h)hh=1;
}
}
}
/*
为了防止抄题解,代码里可能会有废话/ww
管控另外一个领导的定义如下:这个牛所管理的范围可以包含另外一种牛第一次出现的位置。
管理包括所有和自己种类一样的牛的定义如下:这个牛所管理的范围可以包含和自己种类一样的牛最后一次出现的位置。
*/
if(a[g]>=G&&a[h]>=H&&!gg&&!hh)ans++;
cout<<ans;
}