首页 > 代码库 > POJ 1854 贪心
POJ 1854 贪心
链接：
http://poj.org/problem?id=1854
题意：
给你一个字符串，每次你能交换两个相邻的字符，问你最少交换多少次，使它变成回文串
题解：
从两边向中间进行贪心选择，要么更改左边使和右边相等，要么更改右边使和左边相等，取最小的那个就行了
代码：
31 int main() {32 int T;33 cin >> T;34 while (T--) {35 string s;36 cin >> s;37 int n = s.length();38 map<char, int> mmp;39 rep(i, 0, n) mmp[s[i]]++;40 int sum = 0;41 rep(i, ‘a‘, ‘z‘ + 1) if (mmp[i] & 1) sum++;42 if (sum > 1) {43 cout << "Impossible" << endl;44 continue;45 }46 int ans = 0; 47 for (int i = 0, j = n - 1; i < j; i++, j--) {48 int l, r;49 for (r = j; r > i; r--) if (s[i] == s[r]) break;50 for (l = i; l < j; l++) if (s[j] == s[l]) break;51 if (j - r > l - i) {52 ans += l - i;53 per(k, i, l) swap(s[k], s[k + 1]);54 }55 else {56 ans += j - r;57 rep(k, r, j) swap(s[k], s[k + 1]);58 }59 }60 cout << ans << endl;61 }62 return 0;63 }
POJ 1854 贪心
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。