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)


相关推荐

  • Mybatis 动态SQL

    Mybatis 动态SQLMybatis动态SQL一.动态SQL数组array使用foreach标签<!–mybatis的集合操作知识点:如果遇到集合参数传递,需要将集合遍历标签:foreach循环遍历集合标签属性说明:1.collection表示遍历的集合类型1.1数组关键字array1.2List集合关键字lis

  • 视觉SLAM技术_解读团体技术

    视觉SLAM技术_解读团体技术近年来,SLAM技术取得了惊人的发展,领先一步的激光SLAM已成熟的应用于各大场景中,视觉SLAM虽在落地应用上不及激光SLAM,但也是目前研究的一大热点,今天我们就来详细聊聊视觉SLAM的那些事儿。视觉SLAM是什么?视觉SLAM主要是基于相机来完成环境的感知工作,相对而言,相机成本较低,容易放到商品硬件上,且图像信息丰富,因此视觉SLAM也备受关注。目前,视觉SLAM可…

  • Java中HashMap遍历几种方式[通俗易懂]

    Java中HashMap遍历几种方式[通俗易懂]目录一、使用迭代器二、foreach遍历一、使用迭代器第一种:  Mapmap=newHashMap();  Iteratoriter=map.entrySet().iterator();  while(iter.hasNext()){  Map.Entryentry=(Map.Entry)iter.next();  Objectkey…

  • 访问ftp服务器的方法_ftp服务器如何设置访问用户

    访问ftp服务器的方法_ftp服务器如何设置访问用户ftp://127.0.0.1”或“ftp://192.168.0.2”1、DOS下的登录格式。如“ftpftp.bbc.com”。2、浏览器中的登录格式。如“ftp://ftp.bbc.com”。3、FTP客户端应用软件的设置。比如在CuteFTP中 如果使用IE直接登陆FTP,则直接用IE浏览器访问“ftp://主机名@IP地址”,然后在弹出的窗口输入

  • springboot+idea热部署(自动刷新)

    springboot+idea热部署(自动刷新)近来在使用idea做springboot的项目,但是发现每次修改之后我都需要重新将项目关闭再开启,这样比较繁琐,发现通过热部署的方式让我们可以一边修改我们的项目,然后在页面中直接通过刷新展示出来spring为开发者提供了一个名为spring-boot-devtools的模块来使SpringBoot应用支持热部署,提高开发者的开发效率,无需手动重启SpringBoot应用。devtool…

  • 如何在系统中添加字体(添加字体到系统)

    笔者最近在使用win10自带的OneNote笔记本记笔记的时候,发现笔者电脑中没有华文新魏这个字体,最开始以为是OneNote不带有这个字体,经过一段时间的收集资料后发现,是笔者电脑win10系统中不带有这个字体,现将有关概念和字体安装方法做一下记录。字体是win10系统自己带有的,其他的软件自能从win10系统中用调用,而不是说字体是某些软件自带的,比如如果office的PPT中含有华文新魏这个字体,那么OneNote中就必然也含有华文新魏这个字体,并不会存在一个软件有这个字体而另一个软件不含有这个字体

发表回复

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

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