首页 > 其他 > 详细

思维构造,建图——cf1159E

时间:2019-05-17 19:29:20      阅读:152      评论:0      收藏:0      [点我收藏+]

很好的题

/*
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("");
    }        
} 

 

思维构造,建图——cf1159E

原文:https://www.cnblogs.com/zsben991126/p/10882940.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!