题意:
给你一个字符串,通过right、left(指针移动)、up、down(字符变化)将它改成一个回文字符串。现在让你求最小的移动次数。
思路:
因为每次操作都是移动光标或者改变字符串,所以只需要字符前半部分和后半部分进行比较。首先把需要翻转字符的次数记录下来。如果光标不需要来回,一次就可以完成,否则,光标一定是先移动完一边在去另一边,求出最小值就可以。
#include <map> #include <set> #include <cstdio> #include <cstring> #include <algorithm> #include <queue> #include <iostream> #include <stack> #include <cmath> #include <string> #include <vector> #include <cstdlib> //#include <bits/stdc++.h> //#define LOACL #define space " " using namespace std; //typedef long long LL; typedef __int64 Int; typedef pair<int, int> paii; const int INF = 0x3f3f3f3f; const double ESP = 1e-5; const double PI = acos(-1.0); const int MOD = 1e9 + 7; const int MAXN = 1e5 + 10; char str[MAXN]; int main() { int n, p; while (scanf("%d%d", &n, &p) != EOF) { scanf("%s", str + 1); int psum = 0, las, fir; bool flag = true; //把p换到左边 if(p > n/2) p = n + 1 - p; for (int i = 1; i <= n/2; i++) { int op = abs(str[i] - str[n + 1 - i]); if (op) { if (flag) { fir = i; flag = false; } psum += min(op, 26 - op); las = i; } } if (psum == 0) printf("0 "); else if (fir >= p) printf("%d ", las - p + psum); else if (las <= p) printf("%d ", p - fir + psum); else{ printf("%d ", min(2*(p - fir) + las - p, 2*(las - p) + p - fir) + psum); } } return 0; }