第四章排序 6 AcWing 1538. 链表排序

妖狐艹你老母 2023-09-24 13:55 135阅读 0赞

## 第四章 排序 6 AcWing 1538. 链表排序 ##

### 原题链接 ###

[AcWing 1538. 链表排序][AcWing 1538.]

### 算法标签 ###

链表 排序 哈希表

### 思路 ###

依题意模拟

### 笔者代码 ###

#pragma GCC optimize(2)
    #pragma GCC optimize(3)
    #include<bits/stdc++.h>
    using namespace std;
    #define int long long
    #define x first
    #define y second
    #define ump unordered_map
    #define pq priority_queue
    #define pii pair<int, int>
    #define rep(i, a, b) for(int i=a; i<b; ++i)
    #define Rep(i, a, b) for(int i=a; i>=b; --i)
    #define debug(a) cout<<#a<<"="<<a<<endl;
    #define debugi(i) printf("i = %lld\n", i)
    const int N=10005;
    int n, m;
    ump<string, vector<int>> gra;
    vector<int> q[4];
    inline int rd(){
        int s=0, w=1;
        char ch=getchar();
        while(ch<'0'||ch>'9'){
            if(ch=='-'){
                w=-1;    
            }
            ch=getchar();
        }
        while(ch>='0'&&ch<='9'){
            s=s*10+ch-'0';
            ch=getchar();
        }
        return s*w;
    }
    struct Node{
        string id, next;
        // flag 为是否包含在链表中的标志位 flag=0 表示不在链表中 flag=1 表示在链表中
        int val, flag;
    }node[100005];
    bool cmp(Node A, Node B){
        if(A.flag&&B.flag){
            return A.val<B.val;
        }
    }
    signed main(){
        ios::sync_with_stdio(false);
        cin.tie(0);
        cout.tie(0);
        int n;
        string st;
        cin>>n>>st;
        string id, next;
        int val;
        rep(i, 0, n){
            cin>>id>>val>>next;
            node[i].id=id, node[i].val=val, node[i].next=next, node[i].flag=0; 
        }
        int cnt=0;
        rep(i, 0, N){
            bool flag=false;
            rep(i, 0, n){
                if(node[i].id==st){
                    cnt++;
                    st=node[i].next;
                    node[i].flag=1;
                    if(st=="-1"){
                        flag=true;
                        break;
                    }
                }
            }
            if(flag){
                break;
            }
        }
        if(cnt){
        sort(node, node+n, cmp);
        cout<<cnt<<" "<<node[0].id<<"\n";
        rep(i, 0, cnt-1){
            cout<<node[i].id<<" "<<node[i].val<<" "<<node[i+1].id<<"\n";
        }
        cout<<node[cnt-1].id<<" "<<node[cnt-1].val<<" "<<-1<<"\n";
        }else{
            cout<<"0 -1";
        }
        return 0;
        
    }

### 问题 ###

对于AcWing平台测试数据， 无法通过（第三个测试点）  
![在这里插入图片描述][7573d2afe71c439288c4a7d216c9ea3e.png]  
对于PTA平台测试数据， 可以通过  
![在这里插入图片描述][0423dbd7525949c89be0c2e814dd86f4.png]

AcWing平台第三个测试点  
输入

50 29457
    96490 -12 66641
    43869 -20 34026
    67858 -29 44946
    36061 31 40090
    24671 -4 30407
    34026 -27 14537
    26950 -37 43869
    54127 22 12605
    03312 45 24671
    22716 -31 36061
    83095 -49 22716
    00400 -34 44415
    61142 -5 60330
    06507 7 60282
    43010 33 83095
    57777 49 58664
    44354 32 54127
    53957 2 26950
    60282 -32 53957
    01826 9 11720
    40090 -50 40485
    72250 3 65977
    78432 13 -1
    65977 12 60365
    62352 -3 21839
    88528 -44 72250
    29457 -39 67858
    12605 8 43010
    15250 34 06507
    14537 -26 68765
    58664 -25 01826
    49260 26 96490
    21839 23 15250
    94378 -46 49260
    49374 -21 35557
    30407 27 49374
    38661 -40 78709
    40485 14 61142
    59436 -9 44354
    60330 -35 62352
    66641 -14 88528
    12086 -2 94378
    11720 -33 78432
    35557 -1 12086
    78709 18 -1
    42045 10 57777
    44946 35 59436
    68765 29 03312
    44415 43 38661
    60365 15 00400

我的输出

44 40090
    40090 -50 83095
    83095 -49 94378
    94378 -46 88528
    88528 -44 38661
    38661 -40 29457
    29457 -39 26950
    26950 -37 60330
    60330 -35 00400
    00400 -34 11720
    11720 -33 60282
    60282 -32 22716
    22716 -31 67858
    67858 -29 34026
    34026 -27 14537
    14537 -26 58664
    58664 -25 49374
    49374 -21 43869
    43869 -20 66641
    66641 -14 96490
    96490 -12 59436
    59436 -9 61142
    61142 -5 24671
    24671 -4 62352
    62352 -3 12086
    12086 -2 35557
    35557 -1 53957
    53957 2 72250
    72250 3 06507
    06507 7 12605
    12605 8 01826
    01826 9 42045
    42045 10 65977
    65977 12 78432
    78432 13 40485
    40485 14 60365
    60365 15 78709
    78709 18 54127
    54127 22 21839
    21839 23 49260
    49260 26 30407
    30407 27 68765
    68765 29 36061
    36061 31 44354
    44354 32 -1

标准答案

44 40090
    40090 -50 83095
    83095 -49 94378
    94378 -46 88528
    88528 -44 38661
    38661 -40 29457
    29457 -39 26950
    26950 -37 60330
    60330 -35 00400
    00400 -34 60282
    60282 -32 22716
    22716 -31 67858
    67858 -29 34026
    34026 -27 14537
    14537 -26 49374
    49374 -21 43869
    43869 -20 66641
    66641 -14 96490
    96490 -12 59436
    59436 -9 61142
    61142 -5 24671
    24671 -4 62352
    62352 -3 12086
    12086 -2 35557
    35557 -1 53957
    53957 2 72250
    72250 3 06507
    06507 7 12605
    12605 8 65977
    65977 12 40485
    40485 14 60365
    60365 15 78709
    78709 18 54127
    54127 22 21839
    21839 23 49260
    49260 26 30407
    30407 27 68765
    68765 29 36061
    36061 31 44354
    44354 32 43010
    43010 33 15250
    15250 34 44946
    44946 35 44415
    44415 43 03312
    03312 45 -1

### 错误分析 ###

y总代码似乎错过一些值， 虽然最后按照 Key 值升序的顺序将链表重新排序， 但是对于 − 33 -33 −33数据错过了， 实际上， y总代码错过了不少的值， 导致最后答案与笔者偏差较大  
![在这里插入图片描述][b598f28c32294fe9a8ed1b8eed959eb3.png]

![在这里插入图片描述][89b28e32d30a47bb952cb99802682017.png]

### 对于y总提供的代码 ###

#include <iostream>
    #include <algorithm>
    #include <unordered_map>
    #include <vector>
    
    using namespace std;
    
    struct Node
    {
        string address;
        int key;
        string next;
    
        bool operator< (const Node& t) const
        {
            return key < t.key;
        }
    };
    
    int main()
    {
        int n;
        char head[10];
        scanf("%d%s", &n, head);
    
        unordered_map<string, Node> map;
        char address[10], next[10];
        while (n -- )
        {
            int key;
            scanf("%s%d%s", address, &key, next);
            map[address] = {address, key, next};
        }
    
        vector<Node> nodes;
        for (string i = head; i != "-1"; i = map[i].next) nodes.push_back(map[i]);
    
        printf("%d ", nodes.size());
        if (nodes.empty()) puts("-1");
        else
        {
            sort(nodes.begin(), nodes.end());
            printf("%s\n", nodes[0].address.c_str());
            for (int i = 0; i < nodes.size(); i ++ )
            {
                if (i + 1 == nodes.size())
                    printf("%s %d -1\n", nodes[i].address.c_str(), nodes[i].key);
                else
                    printf("%s %d %s\n", nodes[i].address.c_str(), nodes[i].key, nodes[i + 1].address.c_str());
            }
        }
    
        return 0;
    }

AcWing平台测试数据， 可以通过  
![在这里插入图片描述][7cb81b6aa40e4e118342652069436698.png]

PTA平台测试数据， 可以通过  
![在这里插入图片描述][1395bff7bc634b3084bbb737ec67aa0a.png]

笔者暂时未找到原因， 求诸位大佬指导

### 参考文献 ###

[AcWing 1538. 链表排序y总代码][AcWing 1538. _y]

原创不易  
转载请标明出处  
如果对你有所帮助 别忘啦点赞支持哈  
![在这里插入图片描述][9cb4cb80a18345158f8a69e2f196e5b9.png]

[AcWing 1538.]: https://www.acwing.com/problem/content/1540/
[7573d2afe71c439288c4a7d216c9ea3e.png]: https://img-blog.csdnimg.cn/7573d2afe71c439288c4a7d216c9ea3e.png
[0423dbd7525949c89be0c2e814dd86f4.png]: https://img-blog.csdnimg.cn/0423dbd7525949c89be0c2e814dd86f4.png
[b598f28c32294fe9a8ed1b8eed959eb3.png]: https://img-blog.csdnimg.cn/b598f28c32294fe9a8ed1b8eed959eb3.png
[89b28e32d30a47bb952cb99802682017.png]: https://img-blog.csdnimg.cn/89b28e32d30a47bb952cb99802682017.png
[7cb81b6aa40e4e118342652069436698.png]: https://img-blog.csdnimg.cn/7cb81b6aa40e4e118342652069436698.png
[1395bff7bc634b3084bbb737ec67aa0a.png]: https://img-blog.csdnimg.cn/1395bff7bc634b3084bbb737ec67aa0a.png
[AcWing 1538. _y]: https://www.acwing.com/activity/content/code/content/272708/
[9cb4cb80a18345158f8a69e2f196e5b9.png]: https://img-blog.csdnimg.cn/9cb4cb80a18345158f8a69e2f196e5b9.png