PTA A_1052 Linked List Sorting

798236606

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

解：
链表+排序

1. #include<cstdio>
   
2. #include<algorithm>
   
3. 
   
4. using namespace std;
   
5. 
   
6. typedef struct Node{
   
7.     int add, key, next, is_valid;
   
8. }node;
   
9. 
   
10. node a[100010];
    
11. 
    
12. bool cmp1(node a, node b)
    
13. {
    
14.     return a.is_valid > b.is_valid;
    
15. }
    
16. 
    
17. bool cmp2(node a, node b)
    
18. {
    
19.     return a.key < b.key;
    
20. }
    
21. 
    
22. int main(void)
    
23. {   
    
24.     int head, n, i, add, count = 0;
    
25.    
    
26.     scanf("%d %d", &n, &head);
    
27.    
    
28.     if (!n || head == -1)
    
29.     {
    
30.         puts("0 -1");
    
31.         
    
32.         return 0;
    
33.     }
    
34.         
    
35.     for (i = 0; i < n; i++)
    
36.     {
    
37.         scanf("%d", &add);
    
38.         scanf("%d %d", &a[add].key, &a[add].next);
    
39.         a[add].add = add;
    
40.     }
    
41.         
    
42.     for (i = head; i != -1; i = a[i].next, count++)
    
43.         a[i].is_valid = 1;
    
44. 
    
45.     sort(a, a + 100010, cmp1);
    
46.     sort(a, a + count, cmp2);
    
47.    
    
48.     printf("%d %05d\n", count, a[0].add);
    
49.    
    
50.     for (i = 0; i < count - 1; i++)
    
51.         printf("%05d %d %05d\n", a[i].add, a[i].key, a[i + 1].add);
    
52.    
    
53.     printf("%05d %d -1\n", a[i].add, a[i].key);
    
54.         
    
55.     return 0;   
    
56. }

复制代码

此题的坑：可能会有无效的节点， 即不在链表上；可能全是无效节点。