【例71.1】 字典序排序

解题思路

给每个字符绑定原下标，用stable_sort按字符升序排列，相同字符保持原顺序。排序后位置i的元素贡献|原下标-i|，求和。

正确性说明

依题目给出的对应关系逐项处理，位置与原输入保持明确对应。每一步完成当前项的全部贡献，结束后得到所有位置或字符的目标结果。

易错点

普通排序若相同字符重排会改变代价，必须稳定或以原下标作第二关键字。

复杂度

时间O(L log L)，空间O(L)。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    string s;
    cin >> s;
    vector<pair<char, int>> a;
    for (int i = 0; i < int(s.size()); i++)
        a.push_back({s[i], i});
    stable_sort(a.begin(), a.end(),
                [](const pair<char, int> &x, const pair<char, int> &y) {
                    return x.first < y.first;
                });
    long long ans = 0;
    for (int i = 0; i < int(a.size()); i++)
        ans += abs(a[i].second - i);
    cout << ans << "\n";
    return 0;
}