PTA A_1097 Deduplication on a Linked List

798236606

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

解：
链表+排序+哈希

#include<cstdio>
#include<algorithm>

using namespace std;

typedef struct Node{
    int add, key, next, rank;
}node;

node a[100010];
bool is_duplicated[10010];

bool cmp(node a, node b)
{
    return a.rank < b.rank;
}

int main(void)
{
    int head, n;
    
    scanf("%d %d", &head, &n);
    
    for (int i = 0; i < n; i++)
    {
        int add;
        
        scanf("%d", &add);
        scanf("%d %d", &a[add].key, &a[add].next);
        a[add].add = add;
    }

    int cnt = 0, rm_cnt = 0,  j = -n * 2;
    for (int i = head; i != -1; i = a[i].next)
    {
        a[i].rank = j++;
        
        if (is_duplicated[abs(a[i].key)])
        {
            rm_cnt++;
            a[i].rank += n;
        }
        else
        {
            cnt++;
            is_duplicated[abs(a[i].key)] = true;    
        }    
    }
    
    sort(a, a + 100010, cmp);
    
    for (int i = 0; i < cnt - 1; i++)
        printf("%05d %d %05d\n", a[i].add, a[i].key, a[i + 1].add);
    
    printf("%05d %d -1\n", a[cnt - 1].add, a[cnt - 1].key);
    
    if (rm_cnt)
    {
        int last = cnt + rm_cnt - 1;
        
        for (int i = cnt; i < last; i++)
            printf("%05d %d %05d\n", a[i].add, a[i].key, a[i + 1].add);
        
        printf("%05d %d -1", a[last].add, a[last].key);        
    }
        
    return 0;    
}