CF 1701D Permutation Restoration

標籤： cf

有一个长度为 $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');
}