二〇一四蓝桥杯省赛C韦德娱乐1946手机版

题意:

X星球的考古学家发现了一批清朝留下来的密码。 
那一个密码是由A、B、C、D
多样植物的种子串成的队列。 
周详分析发现,那个密码串当初理应是左右对称的(也正是大家说的镜像串)。 
鉴于长时间,当中许五种子脱落了,因此大概会失掉镜像的风味。

你的天职是:
给定一个现行反革命收看的密码串,计算一下从当年的情况,它要至少脱落多少个种子,才大概会变成未来的规范。

输入一行,表示今后看看的密码串(长度不超出1000) 
渴求输出一个正整数,表示至少脱落了有点个种子。

例如,输入: 
ABCBA 
则程序应该出口: 

再例如,输入: 
ABECDCBABC 
则程序应该出口: 
韦德娱乐1946手机版,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;
}

  

发表评论

电子邮件地址不会被公开。 必填项已用*标注

网站地图xml地图