题解：CF1701D Permutation Restoration
$\forall b_i = \lfloor \dfrac{i}{a_i} \rfloor$，等价于 $a_ib_i \le i < a_i(b_i + 1)$，所以有 $\dfrac{i}{b_i + 1} < a_i \le \dfrac{i}{b_i}$。也就是说，每一个 $b_i$ 都会对应一段 $a_i$ 的区间。由于左端点是开区间无法取到 $\dfrac{i}{b_i + 1}$，因此就是就比 $\dfrac{i}{b_i + 1}$ 大的最小整数，也就是 i / (b[i] + 1) + 1；右端点是闭区间，求出不大于 $\dfrac{i}{b_i + 1}$ 的最大整数，也就是 i / b[i]（当然，$b_i$ 为 $0$ 时显然应该是 $n$）。
便于处理，以左端点为关键字进行排序。考虑到随着 $i$ 的变化，每段区间的右端点都会被最先舍去。因此我们对于每一段区间，用贪心的思想取出每段中的右端点构成的集合中的最小的数作为答案。不难想到可以利用优先队列（小根堆）去维护最小值。由于数据经过了排序，所以还需要记录原来的编号，得到的最小值的编号便是原来 $a$ 数组的下标。
于是有了最终代码，加了一些注释便于理解：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
| #include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <queue>
#define init(x) memset (x,0,sizeof (x))
#define ll long long
#define ull unsigned long long
#define INF 0x3f3f3f3f
using namespace std;
const int MAX = 5e5 + 5;
const int MOD = 1e9 + 7;
inline int read ();
int t,n,a[MAX],ans[MAX];
struct node
{
int x,id;
} num[MAX];
priority_queue <pair <int,int>,vector <pair <int,int> >,greater <pair <int,int> > > q;
bool cmp (node xx,node yy)
{
return xx.x < yy.x;
}
int main ()
{
t = read ();
while (t--)
{
n = read ();
for (int i = 1;i <= n;++i)
{
a[i] = read ();
num[i] = {i / (a[i] + 1) + 1,i};
}
sort (num + 1,num + 1 + n,cmp);
while (!q.empty ()) q.pop ();
int j = 1;
for (int i = 1;i <= n;++i)
{
while (j <= n && num[j].x == i)
{
int k = num[j].id;
if (!a[k]) q.push ({n,k});
else q.push ({k / a[k],k});
++j;
}
ans[q.top ().second] = i;
q.pop ();
}
for (int i = 1;i <= n;++i) printf ("%d ",ans[i]);
puts ("");
}
return 0;
}
inline int read ()
{
int s = 0;int f = 1;
char ch = getchar ();
while ((ch < '0' || ch > '9') && ch != EOF)
{
if (ch == '-') f = -1;
ch = getchar ();
}
while (ch >= '0' && ch <= '9')
{
s = s * 10 + ch - '0';
ch = getchar ();
}
return s * f;
}
|
