PTA A_1097 Deduplication on a Linked List

798236606

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

解：
链表+排序+哈希

1. #include<cstdio>
   
2. #include<algorithm>
   
3. 
   
4. using namespace std;
   
5. 
   
6. typedef struct Node{
   
7.     int add, key, next, rank;
   
8. }node;
   
9. 
   
10. node a[100010];
    
11. bool is_duplicated[10010];
    
12. 
    
13. bool cmp(node a, node b)
    
14. {
    
15.     return a.rank < b.rank;
    
16. }
    
17. 
    
18. int main(void)
    
19. {
    
20.     int head, n;
    
21.    
    
22.     scanf("%d %d", &head, &n);
    
23.    
    
24.     for (int i = 0; i < n; i++)
    
25.     {
    
26.         int add;
    
27.         
    
28.         scanf("%d", &add);
    
29.         scanf("%d %d", &a[add].key, &a[add].next);
    
30.         a[add].add = add;
    
31.     }
    
32. 
    
33.     int cnt = 0, rm_cnt = 0,  j = -n * 2;
    
34.     for (int i = head; i != -1; i = a[i].next)
    
35.     {
    
36.         a[i].rank = j++;
    
37.         
    
38.         if (is_duplicated[abs(a[i].key)])
    
39.         {
    
40.             rm_cnt++;
    
41.             a[i].rank += n;
    
42.         }
    
43.         else
    
44.         {
    
45.             cnt++;
    
46.             is_duplicated[abs(a[i].key)] = true;   
    
47.         }   
    
48.     }
    
49.    
    
50.     sort(a, a + 100010, cmp);
    
51.    
    
52.     for (int i = 0; i < cnt - 1; i++)
    
53.         printf("%05d %d %05d\n", a[i].add, a[i].key, a[i + 1].add);
    
54.    
    
55.     printf("%05d %d -1\n", a[cnt - 1].add, a[cnt - 1].key);
    
56.    
    
57.     if (rm_cnt)
    
58.     {
    
59.         int last = cnt + rm_cnt - 1;
    
60.         
    
61.         for (int i = cnt; i < last; i++)
    
62.             printf("%05d %d %05d\n", a[i].add, a[i].key, a[i + 1].add);
    
63.         
    
64.         printf("%05d %d -1", a[last].add, a[last].key);        
    
65.     }
    
66.         
    
67.     return 0;   
    
68. }

复制代码