題目：戳我

　　題意：給定長度為n的字符串，給定初始光標位置p，支持4種操作，left，right移動光標指向，up，down，改變當前光標指向的字符，輸出最少的操作使得字符串為回文。

　　分析：只關注字符串n/2長度，up，down操作是固定不變的，也就是不能優(yōu)化了，剩下就是left，down的操作數(shù)，細想下中間不用管，只關注從左到中間第一個要改變的位置和最后一個要改變的位置即可，具體看代碼。

?

#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> using namespace std; const int M = 1e5+5;int n, p; char str[M]; int main() {while( ~scanf("%d %d", &n, &p ) ) {getchar();gets( str+1 );int sumchg = 0; //up，down的操作總數(shù)int first = 0; //第一個要改變的位置bool firstjd = true;int last = 0; //最后一個要改變的位置for( int i=1; i<=n/2; i++ ) {int d = abs( str[i]-str[n+1-i] );if( d ) {if( firstjd ) {first = i;firstjd = false;}last = i;sumchg += min( d, 26-d ); //選擇up或者down的最小操作數(shù) }}if( p > n/2 ) //由于回文左右對稱，所以p在中間右邊時也可將p當左邊對稱位置計算p = n+1-p;int ret = 0;if( sumchg == 0 ) { //不需要改變輸出0printf("%d\n", ret);continue;}if( first >= p ) //如果p在第一個要改變的左邊，p只能向右走，即執(zhí)行right操作ret += sumchg + last - p; else if( last <= p ) //如果p在最后一個要改變的右邊，p只能向左走，即執(zhí)行l(wèi)eft操作ret += sumchg + p - first;elseret += min( 2*(p-first)+last-p, 2*(last-p)+p-first ) + sumchg; //p在中間，取求向左向右走的最小值printf("%d\n", ret);}return 0; }

?

?

?

?

?

轉(zhuǎn)載于:https://www.cnblogs.com/TaoTaoCome/p/4700216.html

總結(jié)

以上是生活随笔為你收集整理的CodeForces 486C Palindrome Transformation 贪心+抽象问题本质的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。