鱼C论坛

 找回密码
 立即注册
查看: 2105|回复: 0

[技术交流] PTA A_1052 Linked List Sorting

[复制链接]
发表于 2020-2-6 11:13:47 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能^_^

您需要 登录 才可以下载或查看,没有账号?立即注册

x
传送门:https://pintia.cn/problem-sets/994805342720868352/problems/994805425780670464

解:
链表+排序
  1. #include<cstdio>
  2. #include<algorithm>

  3. using namespace std;

  4. typedef struct Node{
  5.     int add, key, next, is_valid;
  6. }node;

  7. node a[100010];

  8. bool cmp1(node a, node b)
  9. {
  10.     return a.is_valid > b.is_valid;
  11. }

  12. bool cmp2(node a, node b)
  13. {
  14.     return a.key < b.key;
  15. }

  16. int main(void)
  17. {   
  18.     int head, n, i, add, count = 0;
  19.    
  20.     scanf("%d %d", &n, &head);
  21.    
  22.     if (!n || head == -1)
  23.     {
  24.         puts("0 -1");
  25.         
  26.         return 0;
  27.     }
  28.         
  29.     for (i = 0; i < n; i++)
  30.     {
  31.         scanf("%d", &add);
  32.         scanf("%d %d", &a[add].key, &a[add].next);
  33.         a[add].add = add;
  34.     }
  35.         
  36.     for (i = head; i != -1; i = a[i].next, count++)
  37.         a[i].is_valid = 1;

  38.     sort(a, a + 100010, cmp1);
  39.     sort(a, a + count, cmp2);
  40.    
  41.     printf("%d %05d\n", count, a[0].add);
  42.    
  43.     for (i = 0; i < count - 1; i++)
  44.         printf("%05d %d %05d\n", a[i].add, a[i].key, a[i + 1].add);
  45.    
  46.     printf("%05d %d -1\n", a[i].add, a[i].key);
  47.         
  48.     return 0;   
  49. }
复制代码


此题的坑:可能会有无效的节点, 即不在链表上;可能全是无效节点。
小甲鱼最新课程 -> https://ilovefishc.com
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

小黑屋|手机版|Archiver|鱼C工作室 ( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)

GMT+8, 2025-7-7 08:28

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

快速回复 返回顶部 返回列表