【题解】HackerRank - Lena Sort

题目

https://www.hackerrank.com/challenges/lena-sort

题意

题目中用伪代码给出一个排序算法，要求构造 1～n 的一个排列，使得排序过程中恰好比较了 k 次。

题解

玄学做法

• 先算出长度为 d 的序列至多至少比较多少次，至多是单调，至少是每次把剩余的数列分成尽可能均匀的两部分。
• 先按至多的方案填，如果填不下去了不行了就按照至少的方案填。保证在填的过程中有解。

官方题解

• https://www.hackerrank.com/challenges/lena-sort/editorial
• 题目等价于构造一个 n 个节点二叉树，使得每个节点深度和为 k。
• 调整法。如果深度为 x 的那一层没有满，就可以把一个深度为 y 叶节点的深度变为 x，深度和减少了 y-x。
• 先把树造成一条链，然后从末端进行调整。

#include <bits/stdc++.h>
#define FOR(i, x, y) for (remove_const<decltype(y)>::type i = (x), _##i = (y); i < _##i; ++i)
#define FORD(i, x, y) for (remove_const<decltype(x)>::type i = (x), _##i = (y); i > _##i; --i)
using namespace std;
const int maxn = 1E5 + 10;
int f[maxn], T, n, d;
int ans[maxn];

inline bool check(int d, int k) {
    return d == -1 || (f[d] <= k && k <= 1LL * d * (d - 1) / 2);
}

void fill(int x, int y, int k, int l, int r) {
    if (x > y) return;
    assert(check(y - x + 1, k));
    int d = y - x;
    k -= d;
    while (d >= 0 && check(d, k)) { // plan A
        ans[l++] = x++;
        k -= --d;
    }
    if (d > 0) { // plan B
        int t = (x + y + 1) / 2;
        while (!check(y - t, k - f[t - x])) --t;
        assert(t > x);
        ans[l] = t;
        fill(x, t - 1, f[t - x], l + 1, l + t - x);
        fill(t + 1, y, k - f[t - x], l + t - x + 1, r);
    }
}

int main() {
    FOR(i, 2, maxn)
        f[i] = i - 1 + f[i / 2] + f[(i - 1) / 2];
    cin >> T;
    while (T--) {
        scanf("%d%d", &d, &n);
        if (!check(d, n)) puts("-1");
        else {
            fill(1, d, n, 1, d);
            FOR(i, 1, d + 1)
                printf("%d%c", ans[i], i == d ? '\n' : ' ');
        }
    }
}