专栏文章

题解：P9291 [ROI 2018] Quick sort

EEgg_eating_master
P9291题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@minw9md0
此快照首次捕获于
2025/12/02 09:23
3 个月前
此快照最后确认于
2025/12/02 09:23
3 个月前
查看原文
这是一个并不正经的乱搞做法。
考虑 O(nlog⁡n)O(n\log n) 怎么做。设 pxp_x 表示 xx 这个数在排列中的位置。从大到小依次让每个数归位，当我们要让 xx 这个数归位时，只要 px≠xp_x\not=x 就一直操作 [px,x][p_x,x] 这个区间，这样每次都能让 x−pxx-p_x 减半，总次数就是 O(nlog⁡n)O(n\log n)。需要大约 3000030000 次操作，无法通过。
注意到一次操作的左端点并不一定需要是 pxp_x，只要和 pxp_x 的奇偶性相同就好了。考虑找到一个最小的 yy，使得 py,py+1,…,pxp_y,p_{y+1},\dots,p_x 的奇偶性全都相同，然后操作 [min⁡i=yxpi,x][\min_{i=y}^xp_i,x] 这个区间。这样的一次操作可以让 [y,x][y,x] 内的所有数到其位置的距离都减半。
容易证明，在随机数据下，这个做法可以让总次数期望乘 12\frac{1}{2}，于是可以通过。
代码CPP
#include<bits/stdc++.h>
#define pii pair<int, int>
#define fi first
#define se second
#define mkp make_pair
using namespace std;
const int maxn = 3005;
int n;
int a[maxn], p[maxn];
vector<pii> ans;
void qsort(int l, int r) {
    ans.push_back(mkp(l, r));
    vector<int> tmp;
    for (int i = l + 1; i <= r; i += 2) tmp.push_back(a[i]);
    for (int i = l; i <= r; i += 2) tmp.push_back(a[i]);
    for (int i = l; i <= r; i++) p[a[i] = tmp[i - l]] = i;
}
signed main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i], p[a[i]] = i;
    for (int i = n; i >= 1; i--)
        while (p[i] != i) {
            int x = i, y = p[i];
            while (x > 1 && p[x - 1] % 2 == p[i] % 2) y = min(y, p[--x]);
            qsort(y, i);
        }
    cout << ans.size() << '\n';
    for (auto x : ans) cout << x.fi << ' ' << x.se << '\n';
    return 0;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...