AcWing 3381. 手机键盘
原题链接
简单
作者:
千岁千岁千
,
2022-07-08 15:38:29
,
所有人可见
,
阅读 140
#include<iostream>
using namespace std;
string str;
int a[26];
int p[26];
int root(int u){
if(p[u]!=u) p[u]=root(p[u]);
return p[u];
}
int main(){
int t=1;
for(int i=0;i<25;i++){
if(i==18) continue;
a[i]=t;
if(i==17||i==24) a[i+1]=t+1;
t=(t+1)%4;
if(t==0) t++;
}
for(int i=0;i<26;i++) p[i]=i;
for(int i=0;i<26;i++){
if(i==2||i==5||i==8||i==11||i==14||i==18||i==21||i==25) continue;
int l=root(i),r=root(i+1);
p[l]=r;
}
while(cin>>str){
int len=str.length();
int res=a[str[0]-'a'];
for(int i=1;i<len;i++){
/*int l,r;
if(str[i]>=str[i-1]) l=i-1,r=i;
else l=i,r=i-1;
if(a[str[r]-'a']>str[r]-str[l]) res+=a[str[i]-'a']+2;
else res+=a[str[i]-'a'];*/ //找规律的做法
int l=root(str[i-1]-'a'),r=root(str[i]-'a');//并查集做法
if(l==r) res+=a[str[i]-'a']+2;
else res+=a[str[i]-'a'];
}
cout<<res<<endl;
}
return 0;
}