题目链接:https://pintia.cn/problem-sets/994805342720868352/problems/994805425780670464
【分析】
题意:根据给定的键值(保证不会有重复)给链表排序。然后输出结点的地址、键值和下一个结点的地址。
思路:这道题还是要比我想象的要深一点。
- 首先,排序。在结构体再加一个tag来标记某个结点在不在此链表中。这样,在重写cmp时,如果tag为false,就把它移到后面去,在的话再进行按键值排序。
- 然后,是结构体的定义。可以直接一个花括号把值赋进去,注意按结构体中定义的顺序。一个新写法,感觉方便很多。
- 定义cnt变量统计有效结点的个数。但是,在排序的时候,范围是到maxn的,因为,node数组的下标是节点的地址,并不是从0开始的,排完序后才是从0开始。
【代码】
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+5;
struct Node{int adr,key,next;bool tag;
}node[maxn];
bool cmp(Node x,Node y)
{return !x.tag||!y.tag?x.tag>y.tag:x.key<y.key;
}
int main()
{int n,st;scanf("%d%d",&n,&st);for(int i=0;i<n;i++){int a,b,c;scanf("%d%d%d",&a,&b,&c);node[a]={a,b,c,false};}int cnt=0;for(int i=st;i!=-1;i=node[i].next){node[i].tag=true;cnt++;}if(!cnt)printf("0 -1\n");else{sort(node,node+maxn,cmp);printf("%d %05d\n",cnt,node[0].adr);for(int i=0;i<cnt;i++){printf("%05d %d ",node[i].adr,node[i].key);if(cnt!=i+1)printf("%05d\n",node[i+1].adr);else printf("-1\n");}}}