博客

奶牛排队，点击跳转​​​​​​​



https://www.acwing.com/problem/content/description/5136/

题意：

有一个长度为n的奶牛序列，每头牛都拿出一张纸条写下了其前方相邻牛的编号以及其后方相邻牛的编号。为首的奶牛前方相邻数字为0，最后的奶牛后方相邻牛记为0。写好的纸条顺序打乱，求奶牛的序列。

题解：

观察可知，前方相邻奶牛为0号的是第一头奶牛的纸条，则该纸条上写下的后方相邻奶牛则排在第二，再找到另一张写有排在第二的奶牛的编号，就能找到排在第四的奶牛，以此类推，可以找到排在2，4，6……号的奶牛，再观察可得，只有排在二号位的奶牛的纸条上会写下排在第一位的奶牛序号，所以用两个数组A和B来记录在纸条上出现的奶牛的序号，A[i]==1&&B[i]==0的就是排在第一位的奶牛，编号为i，接下来就可以求出排在1,3,5……位的奶牛编号。

代码：

#include<bits/stdc++.h>
using namespace std;
const int M=1e6+10;
int ans[200000+10],A[M],B[M];
map<int,int> mp;//用map可以找到后两位的奶牛编号
int main(){
    int n;
    scanf("%d",&n);
    for(int i=0;i<n;i++){
        int a,b;
        scanf("%d %d",&a,&b);
        A[a]++;B[b]++;//分别记录前相邻奶牛和后相邻奶牛编号出现的次数
        mp[a]=b;
    }
    int j=0,t=0;
    for(j=1;j<=n/2;j++){//找到排在2，4，6......位的奶牛编号
        ans[j*2]=mp[t];
        t=mp[t];
    }
    for(j=0;j<=M;j++){//找到排在第1位的奶牛编号
        if(A[j]==1 && B[j]==0){
            t=j;
            break;
        }
    }
    ans[1]=t;
    for(j=3;j<=n;j=j+2){//找到排在第3，5，7......位的奶牛编号
        ans[j]=mp[t];
        t=mp[t];
        if(t==0)break;
    }
    for(int k=1;k<=n;k++){
        printf("%d ",ans[k]);
    }
    return 0;
}

过辣！！！