UVALive 7752 Free Figurines——双向链表

UVALive 7752 Free Figurines——双向链表

题目要求用最少的步数达到目标，所以要从最小的娃娃开始处理，即从1开始，最后处理到n；

然后就是用双向链表模拟，模拟父子关系的连接与断开，假设要把a连接到b，那么首先把a b的所有父节点断开，然后断开b的一个子节点。

写的时候写乱了，把par和son链表的结束标志都设为0了， 导致0的子节点连接到了7之类的错误，这个特判一下就好

#include #include #include #include using namespace std;const int MAXN = 1e5 + 10;int N, a[MAXN], b[MAXN], par[MAXN], son[MAXN], ans;void DeleteSon(int x) { for (int i = par[x]; i; i = par[i]) { //cout << "Delete " << i << " s son" << endl; son[i] = 0; ans++; }}void DeletePar(int x) { if (par[x] == 0) return; DeletePar(par[x]); //cout << "Delete " << x << " s par" << endl; par[x] = 0;}int main() { while (~scanf("%d", &N)) { memset(par, 0, sizeof(par)); memset(son, 0, sizeof(son)); for (int i = 1; i <= N; i++) { scanf("%d", &a[i]); par[i] = a[i]; son[a[i]] = i; } ans = 0; for (int i = 1; i <= N; i++) { scanf("%d", &b[i]); if (par[i] == b[i]) continue; //cout << i << " to " << b[i] << " : " << endl; DeleteSon(i); DeletePar(i); DeleteSon(b[i]); DeletePar(b[i]); if (b[i]) { if (son[b[i]]) { int temp = son[b[i]]; //cout << "Delete " << temp << " s par and " << b[i] << " s son" << endl; par[temp] = 0; son[b[i]] = 0; ans++; } par[i] = b[i]; son[b[i]] = i; ans++; } } printf("%d\n", ans); } return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。