CF1701D 题解

intel_core · 2022-07-22 15:06:52 · 题解

根据 \lfloor \frac{i}{a_i} \rfloor =b_i 可以推出 a_i \in [\lfloor \frac{i}{b_i+1}\rfloor+1,\lfloor \frac{i}{b_i} \rfloor]。

从 1 到 n 依次填数，把可以填 i，填数的上界最小且没有填数的位置填上 i。

因为题目保证必须有一个合法的排列，所以这样填一定可以填出一个合法的排列。

但是这样做的复杂度是 O(n^2) 的。

可以用堆优化，在枚举到 i 的时候把以 i 作为填数下界的位置的编号和上界放进堆里。

可以做到 O(n \log n)。

#include<bits/stdc++.h>
using namespace std;
const int NR=5e5+10;
int n,a[NR],b[NR],l[NR],r[NR];
vector<int>v[NR];
#define pb push_back

struct task{
    int x,id;
    bool operator <(const task &T)const{
        return x>T.x;
    }
};
priority_queue<task>q;

int main(){
    int T;cin>>T;
    while(T--){
        cin>>n;
        for(int i=1;i<=n;i++){
            scanf("%d",&b[i]);
            if(!b[i])l[i]=i+1,r[i]=n;
            else l[i]=i/(b[i]+1)+1,r[i]=i/b[i];
            v[l[i]].pb(i);
        }
        while(!q.empty())q.pop();
        for(int i=1;i<=n;i++){
            for(int x:v[i])q.push((task){r[x],x});
            task tmp=q.top();q.pop();
            a[tmp.id]=i; 
        }
        for(int i=1;i<=n;i++)printf("%d ",a[i]),v[i].clear();
        puts("");
    }
    return 0;
}