CF 1701D Permutation Restoration

有一個長度為 $n$ 的排列 $a$，$b_i = \lfloor \dfrac{i}{a_i} \rfloor$。現在給定陣列 $b$，還原 $a$。

根據 $b_i = \lfloor \dfrac{i}{a_i} \rfloor$ 可以得到 $\dfrac{i}{b_i+1} < a_i \le \dfrac{i}{b_i}$。把每個數字看作一個耗時為單位時間的任務，都有一個可以接受的開始時間和截止時間，這就是經典的排程問題了（演算法導論第三版思考題 16-4 CLRS-16-4）。

考慮貪心，先按照每個任務的開始時間升序排序，對於每個時間點，維護一個包含這個時間點的任務集合，每次選取集合中截止時間最早的。

void solve()
{
    int n;
    scanf("%d", &n);
    std::vector<int> b(n + 1), l(n + 1), r(n + 1);
    for (int i = 1; i <= n; i++)
    {
        scanf("%d", &b[i]);
        l[i] = i / (b[i] + 1) + 1;
        r[i] = b[i] == 0 ? n : i / b[i];
    }
    std::vector<int> id(n + 1), ans(n + 1);
    for (int i = 1; i <= n; i++) id[i] = i;
    std::sort(id.begin() + 1, id.end(),
              [&l](const int a, const int b) { return l[a] < l[b]; });
    std::priority_queue<std::pair<int, int>, std::vector<std::pair<int, int>>,
                        std::greater<std::pair<int, int>>>
        pq;

    for (int i = 1, j = 1; i <= n; i++)
    {
        while (j <= n && l[id[j]] <= i)
        {
            pq.emplace(r[id[j]], id[j]);
            j++;
        }
        ans[pq.top().second] = i;
        pq.pop();
    }
    for (int i = 1; i <= n; i++) printf("%d ", ans[i]);
    putchar('\n');
}