排列 [构造，思维题]

排列 [构造，思维题]

Wannafly Day 2 G

题目来源：comet OJ

分析

在分析之前，我们要再重述一下q数组的求法：对于排列\(p\)，我们对其所有的前缀排序，然后用排序后的顺序的前缀的长度组成排列\(p\)。

其中，前缀之间的比较遵循以下规则： 1. \(min(p_j)\)更小的前缀更小。\((j = 1..i)\) 2. 当\(min(p_j)\)相同时，长度更小的前缀更小。

那么，遵循以上规则，我们其实可以发现一些规律。首先，我们假设一个前缀中最小的\(p_j\)为“决定因子”。那么： 1. 长度最小的前缀的最后一位一定是\(1\)； 2. 比上一个前缀长度更大且排名更靠后的前缀的最后一位一定不为决定因子； 3. 比上一个前缀长度更小且排名更靠后的前缀的最后一位一定为决定因子。

在尝试推出这些结论之前，我们要先确定一个事实：数组q中的前缀的决定因子一定为降序。这里不再证明，应该很好理解。

首先，第一个结论非常容易得出。

而第二个结论：若前缀长度为\(p_j\)，则其决定因子一定大于等于\(p_{j-1}\)的决定因子。又由于它的长度大于\(p_{j-1}\)，所以它包含了\(p_{j-1}\)的前缀，所以其决定因子等于\(p_{j-1}\)的决定因子。所以，其决定因子一定不在最后一位。所以，最后一位的数值对其排名无影响。

而对于第三个结论：若前缀长度为\(p_j\)。由于当前前缀比\(p_{j-1}\)更靠后，且长度更小，说明而\(p_j\)的决定因子更大。那么这个决定因子一定是第一次出现。一个决定因子决定的排序最靠前的前缀一定是以这个决定因子为最后一位。

那么，我们这时直接构造即可。按照之前的原理，我们只需要令\(p_j < p_{j-1}\)的前缀的最后一位为决定因子，它们为从1开始逐个递增。剩下的位置，由于答案要求字典序，则从前到后按字典序填充即可。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

#include <iostream>
#include <algorithm>

#define MAXN 100100

using namespace std;

int q[MAXN], p[MAXN];

int main()
{
    int n;
    cin >> n;

    for (int i = 1; i<=n; i++)
    {
        cin >> q[i];
        p[i] = 0;
    }

    int cnt = 1;
    for (int i = 1; i<=n; i++)
    {
        if (i==1 || q[i]<q[i-1])
            p[q[i]] = cnt++; 
    }

    for (int i = 1; i<=n; i++)
        if (p[i]==0)
            p[i] = cnt++;

    for (int i = 1; i<=n; i++)
        cout << p[i] << " ";
    cout << endl;
}