很好的题
/* 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