90. 字符串轉(zhuǎn)換

時(shí)間限制1000 ms???? 內(nèi)存限制 65536 KB????

題目描述

我們將僅由若干個(gè)同一小寫字母構(gòu)成的字符串稱之為簡(jiǎn)單串，例如"aaaa"是一個(gè)簡(jiǎn)單串，而"abcd"則不是簡(jiǎn)單串。現(xiàn)在給你一個(gè)僅由小寫字母組成的字符串，你需要用最小的花費(fèi)，將其轉(zhuǎn)換成一個(gè)簡(jiǎn)單串。 花費(fèi)的計(jì)算規(guī)則如下：將a到z這26個(gè)小寫字母從左到右排成一排，則每個(gè)字母都有左右兩個(gè)鄰居，我們認(rèn)為a的左鄰居是z，z的右鄰居是a。一個(gè)字母只能轉(zhuǎn)換成其相鄰的字母，轉(zhuǎn)換的花費(fèi)為1。一個(gè)字母可以進(jìn)行多次轉(zhuǎn)換，例如將a轉(zhuǎn)換成d，可以進(jìn)行如下的步驟: a->b->c->d，花費(fèi)為3。字符串的轉(zhuǎn)換花費(fèi)為所有字母轉(zhuǎn)換花費(fèi)之和。例如將字符串"abbbz"轉(zhuǎn)換成簡(jiǎn)單串的最小花費(fèi)為3，轉(zhuǎn)換后的結(jié)果為"bbbbb"。

輸入格式

第一行一個(gè)整數(shù)T?(T≤100?)，表示測(cè)試數(shù)據(jù)的組數(shù)。 每組測(cè)試數(shù)據(jù)只有一行，為僅含小寫字母的字符串，字符串長(zhǎng)度不超過1000。

輸出格式

對(duì)于每一組數(shù)據(jù)，輸出一個(gè)整數(shù)，表示將字符串轉(zhuǎn)換成簡(jiǎn)單串的最小花費(fèi)。

輸入樣例

2 abbba abbac

輸出樣例

2 3

?

先計(jì)算出每個(gè)字母轉(zhuǎn)化為其他字母的耗費(fèi)來，再統(tǒng)計(jì)出每個(gè)字母各出現(xiàn)了多少次，然后枚舉所有的變化即可。

?

#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; }

?

總結(jié)

以上是生活随笔為你收集整理的北邮OJ 90. 字符串转换的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。