贪心+构造 Codeforces Round #277 (Div. 2) C. Palindrome Transformation

题目传送门

 /*
贪心+构造:因为是对称的,可以全都左一半考虑,过程很简单,但是能想到就很难了
*/
/************************************************
Author :Running_Time
Created Time :2015-8-3 9:14:02
File Name :B.cpp
*************************************************/ #include <cstdio>
#include <algorithm>
#include <iostream>
#include <sstream>
#include <cstring>
#include <cmath>
#include <string>
#include <vector>
#include <queue>
#include <deque>
#include <stack>
#include <list>
#include <map>
#include <set>
#include <bitset>
#include <cstdlib>
#include <ctime>
using namespace std; #define lson l, mid, rt << 1
#define rson mid + 1, r, rt << 1 | 1
typedef long long ll;
const int MAXN = 1e5 + ;
const int INF = 0x3f3f3f3f;
const int MOD = 1e9 + ;
char s[MAXN];
int a[MAXN];
int n, p; int main(void) { //Codeforces Round #277 (Div. 2) C. Palindrome Transformation
scanf ("%d%d", &n, &p); scanf ("%s", s + );
if (p > n / ) p = n - p + ;
int l = n + , r = ; int ans = ;
for (int i=; i<=n/; ++i) {
if (s[i] != s[n-i+]) {
l = min (l, i); r = max (r, i);
ans += min (abs (s[i] - s[n-i+]), - abs (s[i] - s[n-i+]));
}
}
if (ans == ) puts ("");
else {
printf ("%d\n", ans + r - l + min (abs (p - l), abs (r - p)));
} return ;
}

下面的图片更形象点。。。

贪心+构造 Codeforces Round #277 (Div. 2) C. Palindrome Transformation

上一篇:Java多线程实现自然同步(内含演示案例)


下一篇:套题 Codeforces Round #277 (Div. 2)