2023年西安交通大学校赛（E-雪中楼)

E.雪中楼

如果算出按南北的序列，再转成从低到高的编号序列，岂不是太麻烦了，幸好，没有在这方面费长时间，而是意识到，本质就是要从低到高的编号序列，所以我就按样例模拟了一下，当a[i]=0时说明编号为i的楼，是前面所有楼中最低的，这时i就该放前面，如果为j,说明它比j高，这时i就该放到j后面。
答案上是用的链表，这样就可以实现，不断插入合适的位置。而我起初用的定义find和insert，查找位置，再插入，果不其然，时间超限。
如果不太会链表，可以看看下面的方法：
既然a[i]=0,就放前面，那我可以从后往前遍历，遇到0，就把i输出，这样就直接放前面了。而遇到其他值就先存起来，存的时候，存两个a[i]和i，也就是i你要放到a[i]后边。当你输出a[i]的时候，就将存储里边接到他后边也输出。记住，先存先出。

代码

#include<bits/stdc++.h>
using namespace std;
map<int,int> q[200005];
void print(int i)
{for(auto it:q[i]){cout<<it.second<<' ';	if(q[it.second].size()!=0)	print(it.second);这里要递归，把接在输出后面的值，也输出}	
}
int main()
{int n,k=0,a[200005];cin>>n;		for(int i=1;i<=n;i++){cin>>a[i];}for(int i=n;i>=1;i--){if(a[i]==0) {cout<<i<<" ";print(i);}elseq[a[i]][k++]+=i;		}
}