120 种输入比较次数总和

把全部 120 种排列的比较次数加总：

#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
using namespace std;

void qs_go(const vector<int>& x, int& c) {
    if (x.size() <= 1) return;
    int p = x[0];                            // 总是拿第一个当枢轴
    c += (int)x.size() - 1;
    vector<int> lo, hi;
    for (size_t k = 1; k < x.size(); k++) (x[k] < p ? lo : hi).push_back(x[k]);
    qs_go(lo, c);
    qs_go(hi, c);
}

int qs_cmp(const vector<int>& a) {
    int c = 0;
    qs_go(a, c);
    return c;
}

vector<vector<int>> all_perms() {
    vector<int> p = {0, 1, 2, 3, 4};
    vector<vector<int>> out;
    do { out.push_back(p); } while (next_permutation(p.begin(), p.end()));
    return out;
}

int main() {
    int sum = 0;
    for (const auto& p : all_perms()) sum += qs_cmp(p);
    cout << sum << endl;
}

（本题用 g++ -std=c++17 -O0 编译。）