北郵OJ 90. 字元串轉換

90. 字元串轉換

時間限制1000 ms     記憶體限制 65536 KB    

題目描述

我們将僅由若幹個同一小寫字母構成的字元串稱之為簡單串，例如"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<stdio.h>
#include<cmath>
#include<string.h>
#define min(a,b) a<b?a:b
#define clr(a) memset(a,0,sizeof a)
using namespace std;
int main(){
    int t,i,j,a[26],b[26][26],ans,tmp;
    char str[1001];
    for(i=0;i<26;i++)
        for(j=0;j<26;j++)
            b[i][j]=min(abs(i-j),26-abs(i-j));
    for(scanf("%d",&t);t--;){
        scanf("%s",str);
        clr(a);
        ans=999999999;
        for(i=0;str[i];i++)
            a[str[i]-'a']++;
        for(i=0;i<26;i++){
            tmp=0;
            for(j=0;j<26;j++)
                tmp+=a[j]*b[j][i];
            ans=min(ans,tmp);
        }
        printf("%d\n",ans);
    }
    return 0;
}