除了上面这一点,本题所要构造的有向图比较特殊,对于一个点 u, 指向它的点的编号都是从 a[u]%n 开始,到 (u+n-1)%n 结束。换句话说一个点要么入度为 0,要么一定会被它前面一个点指向。
还有,构图的目的只是为了拓扑排序。 我们可以用一个环状链表来维护这一过程,链表中的元素会在它被推送到最终输出队列时被删除,那么,只有在删除了从 a[u]%n 到 (u+n-1)%n 的点之后,才可以删除节点 u。为了使拓扑序的字典序最小,我们需要对现在可以删除的节点用小根堆进行维护。
考虑链表和堆的维护,总体时间复杂度是 O(n log n).
至于具体实现,手写双向环状链表自然最快,也可以用 STL 的 list, 由于是环状的,别忘了特殊处理处于 begin() 和 end() 的情况,实测效率会比手写的慢 50% 左右,但也能通过此题 (938ms) ;也可以设 fa[u] 表示如果 u 已经被删除,它右边最近的一个仍然存在的节点是哪一个,然后用并查集去做,这些都是 O(n) 的维护,最慢的自然是 O(n log n) 的线段树做法。
最后贴上用 list 过的代码
#include <cstdio> #include <cstdlib> #include <algorithm> #include <list> #include <cassert> using namespace std; #define aut(a,x) __typeof(x) a=(x) #define rep(i,o,e) for(int i=(o); i<(e); ++i) typedef long long LL; const int N=2e5+5; struct C{int key; int idx; bool ins;}; list<C> c; list<C>::iterator s[N]; int ans[N]; int n; bool hlss(list<C>::iterator p, list<C>::iterator q){ return p->key > q->key; } void xmain(){ int tac; scanf("%d",&tac); rep(tic,0,tac){ scanf("%d",&n); c.clear(); int zs=0, zlast=0; rep(i,0,n){ C t; scanf("%d",&t.key); t.idx = i; t.ins = false; aut(ite, c.insert(c.end(),t)); if(~t.key){ ++zlast; if(t.key%n==i){ s[zs++] = ite; ite->ins = true; } } } int zz=0; make_heap(s,s+zs,hlss); while(zs && zlast){ aut(ite, s[0]); pop_heap(s,s+zs,hlss); --zs; ans[zz++] = ite->key; --zlast; ite = c.erase(ite); if(c.empty())continue; if(ite == c.end() || ite == c.begin()){ if(!c.front().ins && ~c.front().key){ int pos = c.front().key%n; if(c.back().idx < pos || pos <= c.front().idx){ s[zs++] = c.begin(); c.front().ins = true; push_heap(s,s+zs,hlss); } } }else{ if(!ite->ins && ~ite->key){ int pos = ite->key%n; aut(pre, ite); --pre; if(pre->idx < pos && pos <= ite->idx){ s[zs++] = ite; ite->ins = true; push_heap(s,s+zs,hlss); } } } } if(zlast){ puts("-1"); }else{ rep(i,0,zz){ printf("%d",ans[i]); if(i<zz-1)putchar(' '); } puts(""); } } } int main(){ #ifdef LOCAL freopen("in.txt","r",stdin); #endif // LOCAL xmain(); exit(0); }
全部评论
(0) 回帖