2013.网研院.Problem C.字符串转换

野性酷女 2023-07-20 08:25 88阅读 0赞

**题目描述**  
我们将仅由若干个同一小写字母构成的字符串称之为简单串，例如"aaaa"是一个简单串，而"abcd"则不是简单串。现在给你一个仅由小写字母组成的字符串，你需要用最小的花费，将其转换成一个简单串。 花费的计算规则如下：将a到z这26个小写字母从左到右排成一排，则每个字母都有左右两个邻居，我们认为a的左邻居是z，z的右邻居是a。一个字母只能转换成其相邻的字母，转换的花费为1。一个字母可以进行多次转换，例如将a转换成d，可以进行如下的步骤: a->b->c->d，花费为3。字符串的转换花费为所有字母转换花费之和。例如将字符串"abbbz"转换成简单串的最小花费为3，转换后的结果为"bbbbb"。

**输入格式**  
第一行一个整数T(T≤100)，表示测试数据的组数。 每组测试数据只有一行，为仅含小写字母的字符串，字符串长度不超过1000。

**输出格式**  
对于每一组数据，输出一个整数，表示将字符串转换成简单串的最小花费。

**输入样例**

2
    abbba
    abbac

**输出样例**

2
    3

#include<bits/stdc++.h>
    using namespace std;
    int min(int a,int b){ 
    	return a>b?b:a;
    }
    int main() { 
    	int T;
    	string str;
    	int cnt[26];
    	cin>>T;
    	while(T--) { 
    		memset(cnt,0,sizeof(cnt));
    		cin>>str;
    		int len=str.size();
    		for(int i=0; i<len; i++) { 
    			cnt[str[i]-'a']++;
    		}
    		int min_value=100000;
    		for(int i=0; i<26; i++) { 
    			int flag=0;
    			int ans=0;
    			if(cnt[i]!=0) { 
    				for(int j=0; j<26; j++) { 
    					if(cnt[j]!=0){ 
    						flag=1;
    						ans+=(min(abs(j-i),26-abs(j-i)))*cnt[j];
    					}
    				}
    			}
    			if(flag==1&&ans<min_value){ 
    				min_value=ans;
    			}
    		}
    		cout<<min_value<<endl;
    	}
    	return 0;
    }