【例82.2】 座次问题

解题思路

把名字编号为输入顺序0～n-1。枚举这些编号的全部字典序排列，再按编号取名字输出，得到按照报名顺序优先的全排列。

正确性说明

依照上述推导，逐步维护已处理部分的有效状态。每一步都完成当前项的贡献且不改变已确定的次序，结束时输出的状态恰好对应题目要求。

易错点

不是把名字按自身字典序排序。

复杂度

n!种，姓名最长L，时间O(n·n!·L)，空间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> name(n);
    for (auto &s : name)
        cin >> s;
    vector<int> p(n);
    iota(p.begin(), p.end(), 0);
    do {
        for (int i = 0; i < n; i++) {
            if (i)
                cout << " ";
            cout << name[p[i]];
        }
        cout << "\n";
    } while (next_permutation(p.begin(), p.end()));
    return 0;
}