Codeforces 486C Palindrome Transformation(贪心)[通俗易懂]

Codeforces 486C Palindrome Transformation(贪心)

大家好,又见面了,我是全栈君。

题目链接:Codeforces 486C Palindrome Transformation

题目大意:给定一个字符串,长度N。指针位置P,问说最少花多少步将字符串变成回文串。

解题思路:事实上仅仅要是对称位置不同样的。那么指针肯定要先移动到这里,改动字符仅仅须要考虑两种方向哪种更优即

可。

然后将全部须要到达的位置跳出来。贪心处理。

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <vector>
#include <algorithm>

using namespace std;

const int maxn = 1e5 + 5;

int N, P;
vector<int> pos;
char s[maxn];

int solve () {
    int ret = 0, n = N / 2;;
    for (int i = 0; i < n; i++) {
        int tmp = abs(s[i] - s[N-i-1]);
        tmp = min(tmp, 26 - tmp);
        ret += tmp;
        if (tmp)
            pos.push_back(abs(i+1-P) < abs(N-i-P) ? i+1 : N-i);
    }
    n = pos.size();

    if (n == 0)
        return ret;
    sort(pos.begin(), pos.end());
    return ret + pos[n-1] - pos[0] + min(abs(pos[n-1]-P), abs(pos[0]-P));
}

int main () {
    scanf("%d%d%s", &N, &P, s);
    printf("%d\n", solve());
    return 0;
}
版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/115724.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • FPGA–modelsim仿真工具的破解

    FPGA–modelsim仿真工具的破解1、先把modelsim安装到电脑上;2、将解压的破解文件(MentorKG.exe和patch_dll.bat)复制到modelsim安装目录下的win64文件夹中;3、进入安装目录下的win64文件夹找到mgls.dll、mgls64.dll两个文件,去掉只读属性;4、运行patch_dll.bat(双击该文件即可,有的教程是通过cmd运行的,不过没有直接双击方便快捷),稍等一段时…

  • Datadog_DataDog搭建

    Datadog_DataDog搭建这里写目录标题1.Datadog1.1.Datadog新特性1.Datadog1.1.Datadog新特性https://www.datadoghq.com/blog/dash-2021-new-feature-roundup/#infrastructure-and-network-monitoring

    2022年10月22日
  • 串口db9接口定义_db9串口定义及颜色

    串口db9接口定义_db9串口定义及颜色这个接头都是以公头为准,所有接头还是以公头去记.RS-232端(DB9公头/针型)引脚定义2:RXD3:TXD5:GND1/4/6:内部相链接7/8:内部相链接1.RS-232端(D

  • 经典欧美电影推荐

    经典欧美电影推荐

  • 使用javascript实现数组截取

    使用javascript实现数组截取前言:在开发项目的过程中遇到这样的一个问题,就是需要对接口查询出来的数据两个两个的进行截取,之后分别两个两个的放入数组中,再把这些数组放到一个新数组中,实现方法如下:方法一:functionarrayChunk(array,size){ letdata=[]; for(leti=0;i<array.length;i+=size){ data.push(array.slice(i,i+size)) } returndata;}arrayChunk([{i

  • sublime3 激活码【中文破解版】

    (sublime3 激活码)最近有小伙伴私信我,问我这边有没有免费的intellijIdea的激活码,然后我将全栈君台教程分享给他了。激活成功之后他一直表示感谢,哈哈~https://javaforall.cn/100143.htmlIntelliJ2021最新激活注册码,破解教程可免费永久激活,亲测有效,上面是详细链接哦~S32P…

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号