codeforce #277 C. Palindrome Transformation

本文主要是介绍codeforce #277 C. Palindrome Transformation，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

这个题还是比较考思路的。 到时间了都没做出来。 一直WA在第二组样例。 

今早上看了样例之后 知道了 是 没有取绝对值的问题， 取了之后 就AC了。

思路应该是这样的。 如果把一个字符串给变成回文串，其实只需要在字符串的前一半或者后一半走就可以。因为这样总是可以把它改成回文串。

比如 abcde 如果光标在c 你可以在前一半走 改成 edcde 也可以在后一半走  改成 abcba  都是一样的。 再比如 abcd 如果光标在 b 那么一定在前一半走。

改成 dccd。  如果起始光标在 c  一定在后一半走， 改成 abba 修改字符 需要 按键次数就 简单了。 比较一下就可以。

最主要的还是判断怎么走的问题。 

在一个线段上， 假设 光标起始位置 x 在左半边，那么   光标能到达的 最左边假设 是  位置a（a>=1）   光标能到达的最右边 b（b<=（len+1）/2,  len 是字符串长度）

那么现在位置关系就是     a   x    b       len

首先可以肯定的是 x一定需要到达 b 和 a  那么就有 四种方式， 

x 直接走到b 再返回走到 a  需要按键次数 b-a+b-x

x直接走到a 再返回走到 b 需要按键次数 x-a+b-a

也可以 x直接越过b到达 len 再到 a  需要按键次数 len-x+a

也可以 x直接越过a到达len 再到b  需要按键次数 len-b+x

因为我们知道 len +1>=2*b   那么 len-x+a >= 2*b-1-x+a   >   b-a+b-x (a-1 >= -a  ,a>= 1)   ，所以 这种策略 肯定 大 就在后面不比了。

又 len - b + x >= 2*b-1+b+x = b+x-1 > x+b-2*a  ( -1 > -2*a )    , 所以 这种策略 肯定 大 也不考虑了。

所以最后就剩下两种最小的策略， 前两种策略

用 min  取一个小的加上就可以了。

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <string>
#include <algorithm>
#include <fstream>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <list>
#include <vector>
#include <cmath>
#include <iomanip>
#include <cmath>
typedef long long LL;
typedef unsigned long long LLU;
const double PI=acos(-1.0);
using namespace std;
#define MAXN 100000+10
#define INF 1 << 30
int main (){int len,wh;scanf("%d%d",&len,&wh);char s[MAXN];scanf("%s",s+1);LL sum = 0;int co1 = 0,cor = 0;int vis[MAXN] = {0};int co = 0;int mi,ma;if(wh >= len/2){mi = (len+1)/2;ma = len;}else{mi = 1;ma = (len+1)/2;}for(int i = wh,j=wh;;i--,j++){int flag = 0;if(i >= mi){flag = 1;if(s[i] != s[len-i+1]){vis[i] = 1;if(s[i] > s[len-i+1])swap(s[i],s[len-i+1]);sum += min(abs(s[i]-'a'+1+'z'-s[len-i+1]),abs(s[len-i+1]-s[i]));s[i] = s[len-i+1];}}if(j <= ma){flag = 1;if(s[j] != s[len-j+1]){vis[j] = 1;if(s[j] > s[len-j+1])swap(s[j],s[len-j+1]);sum += min(abs(s[j]-'a'+1+'z'-s[len-j+1]),abs(s[len-j+1]-s[j]));s[j] = s[len-j+1];}}if(!flag)break;}int zl = wh,zr = wh;for(int i = mi; i <= ma; i++){if(vis[i]){zl = i;break;}}for(int i = ma; i >= mi; i--){if(vis[i]){zr = i;break;}}int M = INF;M = min(M, min(abs(zr-wh),abs(wh-zl))+zr-zl);//sum += M;printf("%I64d\n",sum);return 0;
}

这篇关于codeforce #277 C. Palindrome Transformation的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---