CF1701D Permutation Restoration题解

· · 题解

CF1701D Permutation Restoration 题解

题目大意

有一个 1\sim n 的排列 a 数组，现在给定所有的 b_i=\left\lfloor\frac{i}{a_i}\right\rfloor，求出对应的 a 数组。

分析

根据 b_i=\left\lfloor\frac{i}{a_i}\right\rfloor 这一条件，我们可以容易的得到 a_i 的范围：

综合一下，就是 \frac{i}{b_i+1}<a_i\le\frac{i}{b_i}。

因此，我们对左端点排序，然后贪心地考虑，每次选择右端点最小的线段，这样的话其他线段有更多的选择空间。

从 1 枚举到 n，当枚举到 i 时，将每一个以 i 为左端点的线段，加入到一个以右端点排序的堆中，每次选择最小的就行了。

Code

#include <stdio.h>
#include <utility>
#include <queue>
#include <algorithm>

struct Node {
    int l, i;
} k [500005];
int b [500005], a [500005];
std :: priority_queue <std :: pair <int, int>, std :: vector <std :: pair <int, int> >, std :: greater <> > Q;//以右端点排序的堆（优先队列），第一维是右端点

bool cmp (Node x, Node y) {
    return x.l < y.l;
}//以左端点排序

int main () {
    int t;
    scanf ("%d", &t);
    while (t --) {
        int n;
        scanf ("%d", &n);
        for (int i = 1; i <= n; ++ i) {
            scanf ("%d", &b [i]);
            k [i] = {i / (b [i] + 1) + 1, i};//左端点和下标
        }

        std :: sort (k + 1, k + n + 1, cmp);//排序

        int cnt = 1;
        for (int i = 1; i <= n; ++ i) {
            while (cnt <= n && k [cnt].l == i) {
                int id = k [cnt].i;
                Q.push ({b [id] == 0 ? n : id / b [id], id});//插入右端点和下标
                ++ cnt;
            }
            a [Q.top ().second] = i;//取出最小值（下标）
            Q.pop ();
        }

        for (int i = 1; i <= n; ++ i)
            printf ("%d ", a [i]);//输出
        printf ("\n");

        while (! Q.empty ()) Q.pop ();
        for (int i = 1; i <= n; ++ i) {
            b [i] = 0;
            a [i] = 0;
            k [i] = {0, 0};
        }//多测记得清空数组
    }
}

完！

记得点个赞！