CF1701D Permutation Restoration

览遍千秋 · 2022-07-14 16:09:49 · 题解

题意简述

Monocarp 有一个由 n 个数字 1, 2, \cdots, n 组成的排列 a。

然后 Monocarp 计算出了一个由 n 个数字组成的数列 b，满足 b_i = \lfloor \dfrac{i}{a_i} \rfloor。

现在 Monocarp 丢掉了排列 a，他希望你可以通过数列 b 倒推出排列 a，如果有多个答案，给出任意一个即可，数据保证有解。

多测，1 \le T \le 10^5, \sum{n} \le 5 \times 10^5

问题分析

由于有 b_i = \lfloor \dfrac{i}{a_i} \rfloor，可以得到 b_i \le \dfrac{i}{a_i} < b_i+1，即 \dfrac{i}{b_i+1} < a_i \le \dfrac{i}{b_i}。

枚举排列 a 中每个数，假设现在枚举到 x。对于每个 x，存在一些线段 S_i，满足 \dfrac{i}{b_i+1} < x \le \dfrac{i}{b_i}。

从贪心的角度来说，对于这些线段，我们选择右端点最小的线段，为其他空留下更多的选择空间。

考虑类似于尺取的方法，从 1 枚举到 n，当枚举到 x 的时候，将所有以 x 为左端点的线段加入到一个以右端点为排序关键字的优先队列中，每次选取最小的即可。

代码实现

#include<bits/stdc++.h>
using namespace std;

typedef long long LL;

template < typename Tp >
void read(Tp &x) {
    x = 0; int fh = 1; char ch = 1;
    while(ch != '-' && (ch < '0' || ch > '9')) ch = getchar();
    if(ch == '-') fh = -1, ch = getchar();
    while(ch >= '0' && ch <= '9') x = x * 10 + ch - '0', ch = getchar();
    x *= fh;
}

const int maxn = 500000 + 7;
int T, n, b[maxn];

void Init(void) {
    read(T);
}

pair <int, pair<int, int> > pr[maxn];
priority_queue < pair<int, int> > Q;
int ans[maxn];

void Work(void) {
    while(T--) {
        for(int i = 1; i <= n; i++) {
            ans[i] = 0; pr[i].first = pr[i].second.first = pr[i].second.second = 0;
        }
        read(n);
//      memset(ans, 0, sizeof(ans));
//      while(!Q.empty()) Q.pop();
//      memset(pr, 0, sizeof(pr));
        for(int i = 1; i <= n; i++) {
            read(b[i]);
            pr[i].first = i / (b[i] + 1) + 1;
            if(b[i] == 0) pr[i].second.first = n;
            else pr[i].second.first = i / b[i];
            pr[i].second.second = i;
        }
        sort(pr + 1, pr + n + 1);
        int cnt = 0;
        for(int i = 1; i <= n; i++) {
            while(cnt <= n && pr[cnt + 1].first == i) {
                Q.push(make_pair(-pr[cnt + 1].second.first, pr[cnt + 1].second.second));
                cnt++;
            }
            int id = Q.top().second; Q.pop();
            ans[id] = i;
        }
        for(int i = 1; i <= n; i++) {
            printf("%d%c", ans[i], " \n"[i == n]);
        }
    }
}

int main(void) {
    Init();
    Work();
    return 0;
}