CF 1701D Permutation Restoration

标签: cf

有一个长度为 的排列 。现在给定数组 ,还原

根据 可以得到 。把每个数字看作一个耗时为单位时间的任务,都有一个可以接受的开始时间和截止时间,这就是经典的调度问题了(算法导论第三版思考题 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');
}