PP4862 港口（基础）

解题思路

第一步，理解题意。 港口先停了一艘"tongchenghao"号，编号是 1。接下来有 n 艘新船，每艘船给出名字、编号和 k，意思是"把这艘新船插到编号为 k 的那艘船的右边"。全部插完后，从童程号开始向右依次输出每艘船的名字和编号。

第二步，想到用链表。 船要不断插到指定位置，还要按顺序输出，这正是链表的典型应用。我们用数组模拟链表：一个数组存船的名字和编号，再用 nxt 数组记录"下一艘船是数组里的哪个下标"，用 nxt=0 表示链表结束。

第三步，找插入的位置。 每来一艘新船，先在链表里从头开始找编号等于 k 的那艘船 p，然后执行"插到 p 后面"：先把新船的下一艘指针指向 p 原来的下一艘，再让 p 指向新船。这两步顺序不能反，否则会丢掉 p 后面的整段链。

第四步，边界情况。 k 一定是已经在链表里的船，所以一定能找到 p。如果插到队尾也没关系，因为 nxt=0 就表示到了结尾。比如样例：先插 zhenzhuhao 到 1 右边，再插 taitanhao 到 4 右边、yangfanhao 到 1 右边，最终顺序正好是 tongchenghao、yangfanhao、zhenzhuhao、taitanhao。

第五步，数据范围。 n 最大 10000，每次找 k 平均要扫一半链表，总操作大约 5000 万次，C++ 完全跑得动。

参考代码

// 港口：用数组模拟链表，把新船插到指定编号船的右边
#include <iostream>
using namespace std;

struct Ship {
    char nm[25];   // 船名
    long long num; // 船编号
    int nxt;       // 指向下一艘船的下标，0 表示没有
};

Ship s[10005];  // 最多 10001 艘船

// 在链表中找编号等于 k 的船，返回它的下标
int find(long long k) {
    int p = 1;
    while (p != 0) {
        if (s[p].num == k) return p;
        p = s[p].nxt;
    }
    return 0;
}

int main() {
    // 初始船 "tongchenghao"，编号 1
    const char* t = "tongchenghao";
    int j = 0;
    while (t[j]) { s[1].nm[j] = t[j]; ++j; }
    s[1].nm[j] = 0;
    s[1].num = 1;
    s[1].nxt = 0;
    int cnt = 1;

    int n;
    cin >> n;
    for (int i = 1; i <= n; ++i) {
        ++cnt;
        long long k;
        cin >> s[cnt].nm >> s[cnt].num >> k;
        int p = find(k);        // 找到插到哪艘船的后面
        s[cnt].nxt = s[p].nxt;  // 新船先指向 p 的下一艘
        s[p].nxt = cnt;         // p 再指向新船
    }
    // 从 1 号船开始依次向右输出
    for (int p = 1; p != 0; p = s[p].nxt) {
        cout << s[p].nm << " " << s[p].num << endl;
    }
    return 0;
}

复杂度分析

插入 n 艘船，第 i 次插入要扫过的链表长度平均约为 i/2，总操作约 n^2/2 次，所以时间复杂度是 O(n^2)；n 最大 10000 时约 5000 万次，能在时限内通过。空间上每个结点只存名字、编号和下一个指针，共 O(n)。