专栏首页小樱的经验随笔Gym 100952C&&2015 HIAST Collegiate Programming Contest C. Palindrome Again !!【字符串,模拟】

Gym 100952C&&2015 HIAST Collegiate Programming Contest C. Palindrome Again !!【字符串,模拟】

C. Palindrome Again !!

time limit per test:1 second

memory limit per test:64 megabytes

input:standard input

output:standard output

Given string with N characters, your task is to transform it to a palindrome string. It's not as easy as you may think because there is a cost for this transformation!!

First you have to start from character at given position P. From your position you always have 2 options:

- You can move one step to the right or to the left, the cost of each movement is 1. Assume that the string is cyclic, this means if you move one step to the left you will be at position P-1 if P > 1 or at the last character if P = 1, and if you move one step to the right you will be at position P+1 if P < N or at first character if P = N.

- You can change the letter at your current position by replacing it with the next or previous one in the English alphabet (assume that the alphabet is also cyclic so ‘a’ is after ‘z’). The cost of each replacement is also 1.

You should repeat that until the transformation is finished and the string is palindrome. What is the minimum cost to do that?

Input

The first line contains the number of test cases T ( 1  ≤  T  ≤  100 ). Each test case contains 2 lines, the first line contains two integers ( 1  ≤  N  ≤  100,000) the length of string and ( 1  ≤  P  ≤  N ) the initial position. While the second line contains a string with exactly N alphabetical characters.

Output

For each test case output one line contains the minimum cost that is needed to change the string into a palindrome one.

Examples

Input

1
8 3
aeabdaey

Output

8

Note

start with P = 3 ae(a)bdaey, move right => aea(b)daey, change to next => aea(c)daey, change to next => aea(d)deay, move left => ae(a)ddeay, move left => a(e)addeay, move left => (a)eaddeay, change to previous => (z)eaddeay, change to previous => (y)eaddeay. This costs 8 (4 movements and 4 replacements)

题目链接:http://codeforces.com/gym/100952/problem/C

题目大意:给出字符串a,将该字符串变成回文串!

分析:

  • 字符串向左边或右边移动一步(0往前移一格为n-1看成环),花费为1
  • 当前字母变为相邻字母,例如a -> b 或 a -> z, 花费为1

模拟此过程操作即可,代码给出了详细注释,一看就懂了!

下面给出AC代码:

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 inline int read()
 4 {
 5     int x=0,f=1;
 6     char ch=getchar();
 7     while(ch<'0'||ch>'9')
 8     {
 9         if(ch=='-')
10             f=-1;
11         ch=getchar();
12     }
13     while(ch>='0'&&ch<='9')
14     {
15         x=x*10+ch-'0';
16         ch=getchar();
17     }
18     return x*f;
19 }
20 inline void write(int x)
21 {
22     if(x<0)
23     {
24         putchar('-');
25         x=-x;
26     }
27     if(x>9)
28         write(x/10);
29     putchar(x%10+'0');
30 }
31 int main()
32 {
33     int t;
34     t=read();
35     while(t--)
36     {
37         int len,p;
38         len=read();
39         p=read();
40         p--;//从零下标开始计数
41         string s;
42         cin>>s;
43         //移动距离
44         int minn=1e+8;
45         int maxn=-1e+8;
46         int ans=0,flag=0;
47         for(int i=0,j=len-1;i<len/2;i++,j--)
48         {
49             if(s[i]!=s[j])
50             {
51                 int a=min(s[i],s[j])-'a';
52                 int b=max(s[i],s[j])-'a';
53                 ans+=min(b-a,a+26-b);//变换需要移动的最短距离
54                 minn=min(minn,i);//满足条件最近的下标值
55                 maxn=max(maxn,i);//满足条件最远的下标值
56                 flag=1;
57             }
58         }
59         if(!flag)//如果序列已经是回文序列
60         {
61             printf("0\n");
62             continue;
63         }
64         if(len%2==1&&p==len/2)//奇数长度的回文序列,查找下标刚好是其中点时
65         {
66             ans+=abs(p-minn);//移动距离为其长度的一半
67             printf("%d\n",ans);
68             continue;
69         }
70         if(p>=len/2)
71             p=len-p-1;//这是一个回文序列,是对称的,所以我们采取序列号从小往大的排列方式
72         int c=abs(minn-p);
73         int d=abs(maxn-p);
74         ans+=min(c,d);//在变换过程中会忽略那些对称的点,所以这步是要加上那些忽略点的距离
75         ans+=(maxn-minn);//起始变换点与变换终点的距离,也就是移动距离
76         printf("%d\n",ans);
77     }
78     return 0;
79 }

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • Codeforces 833E Caramel Clouds

    E. Caramel Clouds time limit per test:3 seconds memory limit per test:256 megaby...

    Angel_Kitty
  • POJ 3662 Telephone Lines【Dijkstra最短路+二分求解】

    Telephone Lines Time Limit: 1000MS Memory Limit: 65536K Total Submission...

    Angel_Kitty
  • HDU 1010 Tempter of the Bone【DFS经典题+奇偶剪枝详解】

    Tempter of the Bone Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 6553...

    Angel_Kitty
  • 1-VIII--ViewPager的基本使用

    张风捷特烈
  • 微信会被封?!包子 Leetcode 1512 solution Number of Good Pairs

    包子君讲解的leetcode题目是越来越简单,在标题党的路上确实越走越远,对不起包子粉了?

    包子面试培训
  • HDUOJ---2642Stars(二维树状数组)

    Stars Time Limit: 5000/2000 MS (Java/Others)    Memory Limit: 32768/65536 K (Jav...

    Gxjun
  • Codeforces 833E Caramel Clouds

    E. Caramel Clouds time limit per test:3 seconds memory limit per test:256 megaby...

    Angel_Kitty
  • 洛谷P2863 [USACO06JAN]牛的舞会The Cow Prom

    ng the other ends of her ropes (if she has any), along with the cows holding the...

    attack
  • 填坑系列(3):扒一扒NVIDIA Tegra Linux 驱动包 (L4T) 32.1里的那些坑

    这个文档里很清楚地描述了目前已知的几个问题(也就是坑),我这里专门挑出跟Jetson NANO相关的,希望用户们在使用过程中注意。当然随着版本的更新,这些问题(...

    GPUS Lady
  • leetcode502. IPO

    Suppose LeetCode will start its IPO soon. In order to sell a good price of its s...

    眯眯眼的猫头鹰

扫码关注云+社区

领取腾讯云代金券