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; }
}