跳至正文

1 条题解

  • 0
    @ 2026-10-7 20:17:45

    【本题解由站长编写】

    贪心:若出现次数为奇数的字母超过 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
    上传者