【例71.2】 01串排序

解题思路

三个排序关键字依次为长度、字符1数量、字典序，全部升序。可直接用自定义比较器按优先级比较。

正确性说明

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

易错点

只有前一关键字相等才比较下一项。

复杂度

每串最长L，时间O(nL log n)，空间O(nL)。

参考代码（C++11）

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    vector<string> a(n);
    for (auto &s : a)
        cin >> s;
    sort(a.begin(), a.end(), [](const string &x, const string &y) {
        if (x.size() != y.size())
            return x.size() < y.size();
        int a = count(x.begin(), x.end(), '1'), b = count(y.begin(), y.end(), '1');
        if (a != b)
            return a < b;
        return x < y;
    });
    for (auto &s : a)
        cout << s << "\n";
    return 0;
}