2月中旬举办了场代码比赛，拉几道我会写的题目来放放（出题人老二次元了）
题目A:这道生物题明明超简单却过分思考
题目详情：
今天正上着生物课呢，老师忽然闻到台下飘来一阵泡面味，仔细一看，原来是泡面在吃小明……噢不是，是小明在吃泡面！老师很生气，于是点名让小明起来回答问题。
老师在黑板上写了一个由大写字母组成的字符串，规定小明每次操作能任选一个字母，让该字母变成在字母表中与其相邻的一个字母，比如字母‘B’可以通过一次操作变成‘A’或‘C’，且规定在字母表中与字母‘Z’相邻的字母是‘Y’和‘A’。而今天课堂上正好学习了核苷酸的四种碱基：腺嘌呤（A）、胸腺嘧啶(T)、胞嘧啶（C）、鸟嘌呤（G）。
于是老师要求小明用最少的操作次数，让黑板上的字母序列中出现“ACTG”这一子串，请问小明最少需要操作多少次能满足老师的要求呢？
- 输入要求
- 第一行输入一个T(1<=T<=50)表示接下来有T组数据
- 第二行输入n（4<=n<=50），表示接下来输入字符串的长度
- 第三行输入字符串s，由n个大写字母组成，表示老师写在黑板上的字符串。
题目分析：
我的方法时采用遍历的方法同时计算四个字符的变换需要的次数取最小值。个人认为这种方法不适用与较大数据的计算，希望看到这篇文章的大佬能给出更好的方法0.0
题目代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
| #include <iostream>
using namespace std;
int dis(char first,char second){
if(first > second){
char temp = first;
first = second;
second = temp;
}
int num = second - first;
return min(26-num,num);
}
int calculate(char words[],int length){
int ans = 666;
int maxnum = 0;
for(int i=0;i+3<length;i++){
maxnum = 0;
maxnum += dis(words[i],'A');
maxnum += dis(words[i+1],'C');
maxnum += dis(words[i+2],'T');
maxnum += dis(words[i+3],'G');
ans = min(maxnum,ans);
}
return ans;
}
int main() {
int num,length;
cin >> num;
for(int i=0;i<num;i++){
char words[50];
cin >> length;
scanf("%s",words);
cout << "Case #" << i+1 << ":"<< endl;
cout <<calculate(words,length) <<endl;
}
}
|