首页 > 代码库 > 2016蓝桥杯省赛C/C++A组第九题 密码脱落
2016蓝桥杯省赛C/C++A组第九题 密码脱落
题意：
X星球的考古学家发现了一批古代留下来的密码。
这些密码是由A、B、C、D 四种植物的种子串成的序列。
仔细分析发现，这些密码串当初应该是前后对称的（也就是我们说的镜像串）。
由于年代久远，其中许多种子脱落了，因而可能会失去镜像的特征。
你的任务是： 给定一个现在看到的密码串，计算一下从当初的状态，它要至少脱落多少个种子，才可能会变成现在的样子。
输入一行，表示现在看到的密码串（长度不大于1000）
要求输出一个正整数，表示至少脱落了多少个种子。
例如，输入：
ABCBA
则程序应该输出：
0
再例如，输入：
ABECDCBABC
则程序应该输出：
3
分析：贪心。
#include<bits/stdc++.h>using namespace std;const int MAXN = 1000 + 10;char s[MAXN];int main(){ scanf("%s", s); int len = strlen(s); int i = 0, j = len - 1; int ans = 0; while(i <= j){ if(s[i] == s[j]){ ++i; --j; } else{ int ti = i; while(ti < j && s[ti] != s[j]){ ++ti; } int tj = j; while(tj >= i && s[tj] != s[i]){ --tj; } if(abs(ti - i) < abs(tj - j)){ ans += abs(ti - i); i = ti; } else{ ans += abs(tj - j); j = tj; } } } printf("%d\n", ans); return 0;}
2016蓝桥杯省赛C/C++A组第九题 密码脱落
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。