PTA A_1052 Linked List Sorting

798236606

传送门：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;    
}

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