E. Text Editor

分析：

每个

i

i

i 都有

b

i

=

?

i

a

i

?

b_i = leftlfloor frac{i}{a_i}
ight
floor

bi?=?ai?i?? ，我们可以将其改写如下：

a

i

?

b

i

≤

i

<

a

i

?

(

b

i

+

1

)

a_i cdot b_i le i < a_i cdot (b_i+1)

ai??bi?≤i<ai??(bi?+1), or

i

b

i

+

1

<

a

i

≤

i

b

i

frac{i}{b_i + 1} < a_i le frac{i}{b_i}

bi?+1i?<ai?≤bi?i?。从这里我们可以看出，每一个

i

i

i 都有一段数值可以分配给

a

i

a_i

ai? 。因此，我们必须将

1

1

1 至

n

n

n 中的每个数字与其中的一个值段匹配起来。

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

1

1

1 枚举到

n

n

n，当枚举到

i

i

i 时，将每一个以

i

i

i 为左端点的线段，加入到一个以右端点排序的堆中，每次选择最小的就行了。

代码：

#include<bits/stdc++.h>
using namespace std;
const int N=5e5+10,M=1e9+10;
typedef long long ll;
typedef pair<int,int> PII;
int T;
vector<PII> g[N];
priority_queue<PII,vector<PII>,greater<PII>> heap;
int ans[N];
void solve()
{
   int n;
   cin>>n;
   int b[N];
   for(int i=1;i<=n;i++) cin>>b[i],g[i].clear();
   for(int i=1;i<=n;i++)
   {
     int l,r;
     if(b[i]==0) l=i+1,r=n;
     else l=i/(b[i]+1) + 1,r=i/b[i];
     g[l].push_back({r,i});
   }
   for(int i=1;i<=n;i++)
   {
    for(auto x : g[i])
       heap.push(x);
    auto t=heap.top();
    heap.pop();
    ans[t.second]=i; 
   }
   for(int i=1;i<=n;i++) cout<<ans[i]<<" 
"[i==n];
   return ;
  }
int main()
{
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>T;
    while(T--) 
    solve();
    return 0;
}