|
马上注册,结交更多好友,享用更多功能^_^
您需要 登录 才可以下载或查看,没有账号?立即注册
x
传送门:https://pintia.cn/problem-sets/994805342720868352/problems/994805425780670464
解:
链表+排序
- #include<cstdio>
- #include<algorithm>
- using namespace std;
- typedef struct Node{
- int add, key, next, is_valid;
- }node;
- node a[100010];
- bool cmp1(node a, node b)
- {
- return a.is_valid > b.is_valid;
- }
- bool cmp2(node a, node b)
- {
- return a.key < b.key;
- }
- int main(void)
- {
- int head, n, i, add, count = 0;
-
- scanf("%d %d", &n, &head);
-
- if (!n || head == -1)
- {
- puts("0 -1");
-
- return 0;
- }
-
- for (i = 0; i < n; i++)
- {
- scanf("%d", &add);
- scanf("%d %d", &a[add].key, &a[add].next);
- a[add].add = add;
- }
-
- for (i = head; i != -1; i = a[i].next, count++)
- a[i].is_valid = 1;
- sort(a, a + 100010, cmp1);
- sort(a, a + count, cmp2);
-
- printf("%d %05d\n", count, a[0].add);
-
- for (i = 0; i < count - 1; i++)
- printf("%05d %d %05d\n", a[i].add, a[i].key, a[i + 1].add);
-
- printf("%05d %d -1\n", a[i].add, a[i].key);
-
- return 0;
- }
复制代码
此题的坑:可能会有无效的节点, 即不在链表上;可能全是无效节点。 |
|