1 条题解
-
0
【本题解由站长编写】
贪心:若出现次数为奇数的字母超过 1 个,无解。否则从两端向中间处理:对左端字符,从右侧未匹配位置找相同字符,通过相邻交换把它冒泡到右端对应位置;若找不到(说明是那个落单的奇数字母),就把它向中间挪一步再继续。交换次数按相邻交换累加。
代码(C++17)
#include <bits/stdc++.h> using namespace std; int main() { int n; string s; cin >> n >> s; int cnt[26] = {0}; for (char c : s) cnt[c - 'a']++; int odd = 0; for (int i = 0; i < 26; i++) if (cnt[i] % 2) odd++; if (odd > 1) { cout << "Impossible" << endl; return 0; } vector<char> v(s.begin(), s.end()); long long swaps = 0; int L = 0, R = n - 1; while (L < R) { int k = R; while (v[k] != v[L]) k--; if (k == L) { swap(v[L], v[L + 1]); swaps++; continue; } for (int m = k; m < R; m++) { swap(v[m], v[m + 1]); swaps++; } L++; R--; } cout << swaps << endl; return 0; }
- 1
信息
- ID
- 4078
- 时间
- 1000ms
- 内存
- 512MiB
- 难度
- 3
- 标签
- 递交数
- 1
- 已通过
- 1
- 上传者