题解 P5462 【X龙珠】

· · 题解

本题大意：给定一个长度为n的1至n的全排列（至少目前数据看起来是这样，值得注意的是，目前题目中并未明确指出是否为全排列，也未说明输入是整数QAQ），每次从排列中选出相邻的两个元素，使它们重新成为一个新的排列，并要求排列的字典序最大。

不难发现，由于要求字典序最大，可以贪心地每次取最大的元素，但需注意，当最大值恰好在序列末尾时，其后没有相邻元素，而最大值和其前面的数组成一对数无法保证字典序最大，这时，次大值成为了最优解……

这样我们可以使用链表和堆来维护答案……但事实上，我们只需从n至1扫一遍，对于扫到的数i，如果i不在目前序列的末尾就可以直接取出，如果i在目前序列的末尾或已被取走就跳过。之所以这么做是正确的，是因为如果i在末尾不能被取走，那么j（j为比i小且未被取走的最大的数，显然，如果扫描了i，下一个必定为j）就一定能被取走，而j一定是目前序列中的次大值且一定能被取走，符合上述贪心策略，得证。

故可以考虑用链表直接维护，但由于本人对链表掌握不好，不过我们可使用了并查集代替链表……

我们可以先以序列上的每个元素为一个集合，建立并查集。(如下图)

假如一个元素x被取出，就让它与其右边第一个与其不在同一集合的元素所在集合合并，这样find(x)后就直接能找到x后第一个未被删除的元素了……（如下图，find(1) = 2, find(3) = 4）

注意本题的一个细节，当我们发现一个元素的右方相邻元素和n为同一集合时，我们能判定其是否在末尾，故我们可令n + 1为尾部，以便我们可以确定如果一个元素的右方相邻元素和n + 1在一个集合中，那么其一定在序列末尾。

Code：

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

namespace Primary
{

const int maxn = 1e5 + 10;

int n, a[maxn], pos[maxn];//pos记录a[i]在序列中的位置
bool used[maxn];

class union_find_set//并查集
{
  private:
    int fa[maxn];

  public:
    inline void init(int bound)
    {
        for (int i = 0; i <= bound; ++i)
            fa[i] = i;
    }

    int find(int x) {return x == fa[x] ? x : fa[x] = find(fa[x]);}

    inline bool unite(int x, int y)
    {
        int fx = find(x), fy = find(y);
        if (fx == fy) return false;
        fa[fx] = fy;
        return true;
    }
}S;

void main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i)
    {
        scanf("%d", a + i);
        pos[a[i]] = i;
        used[i] = false;
    }
    S.init(n + 1);//并查集初始化,注意初始化至n + 1
    for (int i = n; i > 0; --i)
    {
        if (used[i]) continue;
        if (S.find(pos[i] + 1) <= n)//判断a[i]是是否为最后一个
        {
            printf("%d %d ", i, a[S.find(pos[i] + 1)]);
            used[i] = true, used[a[S.find(pos[i] + 1)]] = true;//标记为已输出
            S.unite(pos[i] + 1, S.find(pos[i] + 1) + 1);//更新i与i后面的元素的并查集
            S.unite(pos[i], pos[i] + 1);
        }
    }
}

}

int main()
{
    Primary::main();
    return 0;   
}