抱歉，您的浏览器无法访问本站

本页面需要浏览器支持（启用）JavaScript


了解详情 >

ARC080E Young Maids

This is a picture without description

pufanyi

题解

发布于：Apr 14, 2019

原题链接

题意大概就是给你一个排列 pp，你每次可以找到pp 中相邻两个数并将其移至另一个初始为空的队列的开头，让最终 pp 的字典序尽量小。

过程大概就是这样：

题解

由于字典序大小是从前往后决定的，所以我们考虑从前往后确定这个序列，也就是将题意中的过程倒着做。

我们考虑在某一状态下，选择的两个数在原序列中是 pl,prp_l,p_r，那么再次之前的选择中，不可能出现选择的数为pal,parp_{a_l},p_{a_r} 使得 al<l<ara_l<l<a_r 或al<r<ara_l<r<a_r。

于是我们发现倒着考虑是，选择 pl,prp_l,p_r 时就是把序列分成了 [1,l−1],[l+1,r−1],[r+1,n][1,l-1],[l+1,r-1],[r+1,n] 这33段，这 33 段相互独立。

我们考虑怎样的 <l,r><l,r> 是合法的。显然就是 [1,l−1],[l+1,r−1],[r+1,n][1,l-1],[l+1,r-1],[r+1,n] 长度均为偶数时（可能为空）。

所以 ll 一定为奇数，rr一定为偶数。

我们可以维护出 pp 中奇数位于偶数位的最小值，并用一个小根堆维护每一个 [l,r][l,r] 的最小值即可，每次选择后将 [l,r][l,r] 分成 33 段重新放入堆中。

代码

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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
#include <bits/stdc++.h>

using namespace std;

// 读入输出优化略去 

const int maxn = 200005;
const int inf = 0x3f3f3f3f;

int n;
int xx[maxn]; // 题意中的 p

#define ls(x) (x << 1)
#define rs(x) (x << 1 | 1)

struct Tree
{
    struct Node
    {
        int jx, ox; // 奇数位的最小值与偶数位的最小值
    } no[maxn << 2];

    int k;

    inline int minn(int a, int b)
    {
        if (!a || !b)
            return a | b;
        else
            return xx[a] < xx[b] ? a : b;
    }

    inline void push_up(int k)
    {
        no[k].jx = minn(no[ls(k)].jx, no[rs(k)].jx);
        no[k].ox = minn(no[ls(k)].ox, no[rs(k)].ox);
    }

    inline void build_tree(int n)
    {
        for (k = 1; k <= n; k <<= 1);
        for (int i = 1; i <= n; ++i)
        {
            if (i & 1)
                no[i + k].jx = i;
            else
                no[i + k].ox = i;
        }
        for (int i = k; i; --i)
            push_up(i);
    }

    inline int query(int l, int r, int kk)
    {
        int ans = 0;
        for (l += k - 1, r += k + 1; l ^ r ^ 1; l >>= 1, r >>= 1)
        {
            if (~l & 1)
                ans = minn(kk ? no[l ^ 1].jx : no[l ^ 1].ox, ans);
            if (r & 1)
                ans = minn(kk ? no[r ^ 1].jx : no[r ^ 1].ox, ans);
        }
        return ans;
    }
} tr;

struct QJ
{
    int l, r, ansl, ansr; // 现在可选区间为[l,r]，最优是选择 p[l] 和 p[r]

    friend bool operator < (QJ a, QJ b)
    {
        return xx[a.ansl] > xx[b.ansl];
    }

    QJ (int l, int r)
    {
        this->l = l;
        this->r = r;
        this->ansl = tr.query(l, r, 1);
        this->ansr = tr.query(ansl + 1, r, 0);
    }
};

priority_queue<QJ> q;

int main()
{
    read(n);
    for (int i = 1; i <= n; ++i)
        read(xx[i]);
    tr.build_tree(n);
    q.push(QJ(1, n));
    while (!q.empty())
    {
        QJ now = q.top();
        q.pop();
        writesp(xx[now.ansl]);
        writesp(xx[now.ansr]);
        if (now.ansl + 1 < now.ansr - 1)
            q.push(QJ(now.ansl + 1, now.ansr - 1));
        if (now.l < now.ansl - 1)
            q.push(QJ(now.l, now.ansl - 1));
        if (now.ansr + 1 < now.r)
            q.push(QJ(now.ansr + 1, now.r));
    }
    return 0;
}

博客内容遵循 署名-非商业性使用-相同方式共享 4.0 国际 (CC BY-NC-SA 4.0) 协议

本文永久链接是：https://pufanyi.github.io/oi-blog/arc080_c/

更新于：Jul 7, 2023

贪心

AtCoder

评论