思维构造,建图——cf1159E

很好的题

/*
nexti:pi右边第一个比pi大的数的下标 
把每个[i,a[i]]都看成一段区间,区间只能在端点处交叉,以此来判断是否有解
特别的,如果a[i]=-1,那么把a[i]=i+1,不对其他区间造成任何影响
如何判区间合法性:用一个set记录区间右边界,每次遍历到左端点i时将set里的i删去,然后放入右边界a[i],同时进行判断 
如何输出解 :从n+1开始,右端点向左端点连边,然后拓扑排序(bfs)即可 
*/
#include<bits/stdc++.h>
#include<queue>
using namespace std;
#define maxn 500005
int n,a[maxn],t,ans[maxn];
vector<int>G[maxn];
 
int main(){
    cin>>t;
    while(t--){
        cin>>n;
        for(int i=1;i<=n+1;i++)G[i].clear();
        set<int>s;
        int flag=0;
        
        for(int i=1;i<=n;i++)scanf("%d",&a[i]); 
        for(int i=1;i<=n;i++){
            if(a[i]==-1)a[i]=i+1;
            while(s.find(i)!=s.end())
                s.erase(i);
            if(!s.empty() && *s.begin()<a[i])flag=1;
            s.insert(a[i]);
            G[a[i]].push_back(i);
        }
        
        if(flag){puts("-1");continue;}
        int id=n;
        queue<int>q;q.push(n+1);
        
        while(!q.empty()){
            int u=q.front();q.pop();
            for(int i=0;i<G[u].size();i++){
                int v=G[u][i];
                ans[v]=id--;
                q.push(v);
            }
        }        
        for(int i=1;i<=n;i++)cout<<ans[i]<<" ";
        puts("");
    }        
} 

 

转载于:https://www.cnblogs.com/zsben991126/p/10882940.html

    原文作者:weixin_30274627
    原文地址: https://blog.csdn.net/weixin_30274627/article/details/97418012
    本文转自网络文章,转载此文章仅为分享知识,如有侵权,请联系博主进行删除。
点赞