一、问题描述

题目解析

题目描述

有 N 个快递站点用字符串标识，某些站点之间有道路连接。每个站点有一些包裹要运输，每个站点间的包裹不重复。路上有检查站会导致部分货物无法通行，计算哪些货物无法正常投递。

输入描述

1. 第一行输入 M N，表示有 M 个包裹和 N 条道路信息。
   • 0 <= M, N <= 100。
2. 接下来的 M 行，每行描述一个包裹的运输信息，格式为：包裹名 起点 终点。
3. 接下来的 N 行，每行描述一条道路的限制信息，格式为：起点 终点 包裹名，表示从 起点 到 终点 的道路禁止通行该包裹。

输出描述

输出不能送达的包裹，如：package2 package4。如果所有包裹都可以送达，则输出 none。输出结果按照升序排列。

用例

输入

4 2
package1 A C
package2 A C
package3 B C
package4 A C
A B package1
A C package2

输出

package2

说明

• A-B 无法通行 package1，但 package1 的运输路径是 A-C，不受影响。
• A-C 无法通行 package2，而 package2 的运输路径是 A-C，因此无法送达。
• 最终只有 package2 无法送达。

---

题目解析

问题分析

1. 目标
   根据包裹的运输路径和道路限制信息，判断哪些包裹无法正常送达。

2. 关键点

   • 每个包裹有唯一的运输路径（起点和终点）。
   • 每条道路限制某些包裹的通行。
   • 需要检查每个包裹的运输路径是否被限制。

3. 问题转化
   对于每个包裹，检查其运输路径是否被任何一条道路限制。如果被限制，则该包裹无法送达。

---

解题思路

1. 输入解析

   • 读取 M 和 N，表示包裹数量和道路限制数量。
   • 读取 M 行包裹信息，存储每个包裹的运输路径。
   • 读取 N 行道路限制信息，存储每条道路的限制。

2. 检查包裹是否被限制

   • 对于每个包裹，遍历所有道路限制信息，检查其运输路径是否被限制。
   • 如果运输路径被限制，则将该包裹标记为无法送达。

3. 输出结果

   • 将所有无法送达的包裹按升序排序。
   • 如果没有包裹无法送达，则输出 none；否则输出无法送达的包裹。

---

示例分析

输入

4 2
package1 A C
package2 A C
package3 B C
package4 A C
A B package1
A C package2

步骤

1. 解析输入：

   • 包裹信息：
     • package1: A -> C
     • package2: A -> C
     • package3: B -> C
     • package4: A -> C
   • 道路限制信息：
     • A B package1
     • A C package2

2. 检查每个包裹：

   • package1：运输路径为 A -> C，限制信息为 A B package1，不影响 A -> C，因此可以送达。
   • package2：运输路径为 A -> C，限制信息为 A C package2，影响 A -> C，因此无法送达。
   • package3：运输路径为 B -> C，无限制信息，可以送达。
   • package4：运输路径为 A -> C，无限制信息，可以送达。

3. 输出结果：

   • 无法送达的包裹为 package2。
   • 输出：package2。

---

复杂度分析

1. 时间复杂度

   • 解析输入：O(M + N)。
   • 检查包裹是否被限制：O(M * N)。
   • 排序无法送达的包裹：O(k log k)，其中 k 是无法送达的包裹数量。
   • 总时间复杂度：O(M * N + k log k)。

2. 空间复杂度

   • 存储包裹信息和道路限制信息：O(M + N)。
   • 存储无法送达的包裹：O(k)。
   • 总空间复杂度：O(M + N + k)。

---

总结

本题的核心是通过遍历包裹的运输路径和道路限制信息，判断哪些包裹无法送达。关键在于：

1. 解析输入并存储包裹和道路限制信息。
2. 检查每个包裹的运输路径是否被限制。
3. 输出无法送达的包裹，按升序排序。
4. 时间复杂度为 O(M * N + k log k)，适合处理最大 M 和 N 为 100 的输入。

二、JavaScript算法源码

以下是对这段JavaScript代码的详细注释和讲解：

---

代码功能概述

这段代码用于解决一个包裹运输问题。输入包括：

1. 包裹运输需求：每个需求包含包裹ID、起始站点和目的站点。
2. 运输限制条件：每个限制条件包含起始站点、目的站点以及不能通行的包裹ID列表。

程序的目标是找出所有无法运输的包裹ID，并按照包裹ID中的数字部分排序后输出。

---

代码详细注释

/* JavaScript Node ACM模式 控制台输入获取 */
const readline = require("readline");

// 创建readline接口，用于从控制台读取输入
const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout,
});

// 存储输入行的数组
const lines = [];
let m, n; // m: 包裹运输需求的条数，n: 限制条件的条数
let want, cant; // want: 包裹运输需求，cant: 运输限制条件

// 监听每一行输入
rl.on("line", (line) => {
  lines.push(line); // 将输入行存入lines数组

  // 第一行输入是m和n
  if (lines.length === 1) {
    [m, n] = lines[0].split(" ").map(Number); // 解析m和n
  }

  // 当输入行数达到m+1时，表示包裹运输需求输入完毕
  if (m !== undefined && lines.length === m + 1) {
    want = lines.slice(1).map((line) => line.split(" ")); // 解析want数组
  }

  // 当输入行数达到m+n+1时，表示运输限制条件输入完毕
  if (n !== undefined && lines.length === m + n + 1) {
    cant = lines.slice(m + 1).map((line) => line.split(" ")); // 解析cant数组

    // 调用getResult函数计算结果并输出
    console.log(getResult(want, cant));
    lines.length = 0; // 清空lines数组，准备下一组输入
  }
});

/**
 * @param {*} want 二维数组，元素是 [包裹， 起始站点， 目的站点]
 * @param {*} cant 二维数组，元素是 [起始站点， 目的站点，...无法通行的货物列表]
 * @returns 无法通行的包裹ID，按数字部分排序后拼接成字符串
 */
function getResult(want, cant) {
  const wantObj = {}; // 存储路径对应的包裹ID列表
  const cantObj = {}; // 存储路径对应的限制包裹ID列表

  // 遍历want数组，填充wantObj
  for (let arr of want) {
    const [package, src, dst] = arr; // 解构赋值：包裹ID、起始站点、目的站点
    const path = `${src}-${dst}`; // 构建路径字符串，如"A-B"
    wantObj[path] ? wantObj[path].push(package) : (wantObj[path] = [package]); // 将包裹ID加入对应路径的列表
  }

  // 遍历cant数组，填充cantObj
  for (let arr of cant) {
    const src = arr[0]; // 起始站点
    const dst = arr[1]; // 目的站点
    const path = `${src}-${dst}`; // 构建路径字符串

    const packages = arr.slice(2); // 获取限制包裹ID列表
    cantObj[path] ? cantObj[path].push(...packages) : (cantObj[path] = [...packages]); // 将限制包裹ID加入对应路径的列表
  }

  let ans = []; // 存储无法运输的包裹ID

  // 遍历wantObj中的每个路径
  for (let path in wantObj) {
    const wantPKG = new Set(wantObj[path]); // 当前路径需要运输的包裹ID集合
    const cantPKG = new Set(cantObj[path]); // 当前路径限制运输的包裹ID集合

    // 遍历需要运输的包裹ID
    wantPKG.forEach((pkg) => {
      if (cantPKG.has(pkg)) {
        ans.push(pkg); // 如果包裹ID在限制列表中，加入结果数组
      }
    });
  }

  // 如果没有无法运输的包裹，返回"none"
  if (!ans.length) return "none";

  // 对结果数组按包裹ID的数字部分排序
  return ans
    .sort((a, b) => Number(a.slice(7)) - Number(b.slice(7))) // 假设包裹ID格式为"packageX"
    .join(" "); // 将排序后的包裹ID拼接成字符串
}

---

代码逻辑详解

1. 输入处理：

   • 使用readline模块逐行读取输入。
   • 第一行输入是m和n，分别表示包裹运输需求的条数和限制条件的条数。
   • 接下来的m行是包裹运输需求，存储在want数组中。
   • 接下来的n行是运输限制条件，存储在cant数组中。

2. 数据结构：

   • wantObj：一个对象，键是路径（如"A-B"），值是该路径需要运输的包裹ID列表。
   • cantObj：一个对象，键是路径，值是该路径限制运输的包裹ID列表。

3. 填充wantObj和cantObj：

   • 遍历want数组，将每个包裹ID加入对应路径的列表。
   • 遍历cant数组，将每个限制包裹ID加入对应路径的列表。

4. 查找无法运输的包裹：

   • 遍历wantObj中的每个路径，检查该路径需要运输的包裹ID是否在cantObj的限制列表中。
   • 如果存在限制，将包裹ID加入结果数组ans。

5. 结果处理：

   • 如果ans为空，返回"none"。
   • 否则，对ans中的包裹ID按数字部分排序（假设包裹ID格式为packageX），并拼接成字符串返回。

---

示例运行

输入：

3 2
package1 A B
package2 A C
package3 B C
A B package1 package2
B C package3

输出：

package1 package3

解释：

• 路径A-B限制运输package1和package2，但只有package1在需求列表中。
• 路径B-C限制运输package3，且package3在需求列表中。
• 最终输出无法运输的包裹ID：package1 package3。

---

总结

这段代码通过合理的数据结构（对象和集合）和逻辑处理，高效地解决了包裹运输问题。代码结构清晰，注释详细，适合用于需要处理大量输入并进行复杂逻辑判断的场景。

三、Java算法源码

以下是对这段Java代码的详细注释和讲解：

---

代码功能概述

这段代码用于解决一个包裹运输问题。输入包括：

1. 包裹运输需求：每个需求包含包裹ID、起始站点和目的站点。
2. 运输限制条件：每个限制条件包含起始站点、目的站点以及不能通行的包裹ID列表。

程序的目标是找出所有无法运输的包裹ID，并按照包裹ID中的数字部分排序后输出。

---

代码详细注释

import java.util.*;

public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in); // 创建Scanner对象，用于读取输入

    // 读取第一行输入，解析m和n
    Integer[] tmp =
        Arrays.stream(sc.nextLine().split(" ")) // 将输入行按空格分割成字符串数组
              .map(Integer::parseInt) // 将字符串转换为整数
              .toArray(Integer[]::new); // 转换为Integer数组
    int m = tmp[0]; // m: 包裹运输需求的条数
    int n = tmp[1]; // n: 限制条件的条数

    // 读取m行包裹运输需求，存储在want数组中
    String[][] want = new String[m][];
    for (int i = 0; i < m; i++) {
      want[i] = sc.nextLine().split(" "); // 将每行按空格分割成字符串数组
    }

    // 读取n行运输限制条件，存储在cant数组中
    String[][] cant = new String[n][];
    for (int i = 0; i < n; i++) {
      cant[i] = sc.nextLine().split(" "); // 将每行按空格分割成字符串数组
    }

    // 调用getResult函数计算结果并输出
    System.out.println(getResult(want, cant));
  }

  /**
   * @param want 二维数组，元素是 [包裹， 起始站点， 目的站点]
   * @param cant 二维数组，元素是 [起始站点， 目的站点，...无法通行的包裹列表]
   * @return 无法通行的包裹ID，按数字部分排序后拼接成字符串
   */
  public static String getResult(String[][] want, String[][] cant) {
    // 使用HashMap存储路径对应的包裹ID集合
    HashMap<String, HashSet<String>> wantMap = new HashMap<>(); // 存储运输需求
    HashMap<String, HashSet<String>> cantMap = new HashMap<>(); // 存储运输限制

    // 遍历want数组，填充wantMap
    for (String[] arr : want) {
      String pkg = arr[0]; // 包裹ID
      String path = arr[1] + "-" + arr[2]; // 构建路径字符串，如"A-B"
      wantMap.putIfAbsent(path, new HashSet<>()); // 如果路径不存在，初始化一个空集合
      wantMap.get(path).add(pkg); // 将包裹ID加入对应路径的集合
    }

    // 遍历cant数组，填充cantMap
    for (String[] arr : cant) {
      String path = arr[0] + "-" + arr[1]; // 构建路径字符串
      String[] pkgs = Arrays.copyOfRange(arr, 2, arr.length); // 获取限制包裹ID列表
      cantMap.putIfAbsent(path, new HashSet<>()); // 如果路径不存在，初始化一个空集合
      cantMap.get(path).addAll(Arrays.asList(pkgs)); // 将限制包裹ID加入对应路径的集合
    }

    ArrayList<String> ans = new ArrayList<>(); // 存储无法运输的包裹ID

    // 遍历wantMap中的每个路径
    for (String path : wantMap.keySet()) {
      HashSet<String> wantPKG = wantMap.get(path); // 当前路径需要运输的包裹ID集合
      HashSet<String> cantPKG = cantMap.get(path); // 当前路径限制运输的包裹ID集合

      if (cantPKG == null) continue; // 如果当前路径没有限制，跳过

      // 遍历需要运输的包裹ID
      for (String pkg : wantPKG) {
        if (cantPKG.contains(pkg)) {
          ans.add(pkg); // 如果包裹ID在限制列表中，加入结果列表
        }
      }
    }

    // 如果没有无法运输的包裹，返回"none"
    if (ans.size() == 0) return "none";

    // 对结果列表按包裹ID的数字部分排序
    ans.sort((a, b) -> Integer.parseInt(a.substring(7)) - Integer.parseInt(b.substring(7))); // 假设包裹ID格式为"packageX"

    // 使用StringJoiner将排序后的包裹ID拼接成字符串
    StringJoiner sj = new StringJoiner(" ");
    for (String an : ans) {
      sj.add(an);
    }
    return sj.toString();
  }
}

---

代码逻辑详解

1. 输入处理：

   • 使用Scanner类从标准输入中读取数据。
   • 第一行输入是m和n，分别表示包裹运输需求的条数和限制条件的条数。
   • 接下来的m行是包裹运输需求，存储在want数组中。
   • 接下来的n行是运输限制条件，存储在cant数组中。

2. 数据结构：

   • wantMap：一个HashMap，键是路径（如"A-B"），值是该路径需要运输的包裹ID集合（HashSet）。
   • cantMap：一个HashMap，键是路径，值是该路径限制运输的包裹ID集合。

3. 填充wantMap和cantMap：

   • 遍历want数组，将每个包裹ID加入对应路径的集合。
   • 遍历cant数组，将每个限制包裹ID加入对应路径的集合。

4. 查找无法运输的包裹：

   • 遍历wantMap中的每个路径，检查该路径需要运输的包裹ID是否在cantMap的限制集合中。
   • 如果存在限制，将包裹ID加入结果列表ans。

5. 结果处理：

   • 如果ans为空，返回"none"。
   • 否则，对ans中的包裹ID按数字部分排序（假设包裹ID格式为packageX），并使用StringJoiner拼接成字符串返回。

---

示例运行

输入：

3 2
package1 A B
package2 A C
package3 B C
A B package1 package2
B C package3

输出：

package1 package3

解释：

• 路径A-B限制运输package1和package2，但只有package1在需求列表中。
• 路径B-C限制运输package3，且package3在需求列表中。
• 最终输出无法运输的包裹ID：package1 package3。

---

总结

这段代码通过合理的数据结构（HashMap和HashSet）和逻辑处理，高效地解决了包裹运输问题。代码结构清晰，注释详细，适合用于需要处理大量输入并进行复杂逻辑判断的场景。

四、Python算法源码

以下是对这段Python代码的详细注释和讲解：

---

代码功能概述

这段代码用于解决一个包裹运输问题。输入包括：

1. 包裹运输需求：每个需求包含包裹ID、起始站点和目的站点。
2. 运输限制条件：每个限制条件包含起始站点、目的站点以及不能通行的包裹ID列表。

程序的目标是找出所有无法运输的包裹ID，并按照包裹ID中的数字部分排序后输出。

---

代码详细注释

# 输入获取
m, n = map(int, input().split())  # 读取m和n，分别表示包裹运输需求的条数和限制条件的条数

want = []  # 存储包裹运输需求
for i in range(m):
    want.append(input().split())  # 读取每行包裹运输需求，按空格分割成列表并存入want

cant = []  # 存储运输限制条件
for i in range(n):
    cant.append(input().split())  # 读取每行运输限制条件，按空格分割成列表并存入cant


# 算法入口
def getResult(want, cant):
    """
    :param want: 二维数组，元素是 [包裹， 起始站点， 目的站点]
    :param cant: 二维数组，元素是 [起始站点， 目的站点，...无法通行的货物列表]
    :return: 不能送达的包裹
    """
    wantDict = {}  # 存储路径对应的包裹ID列表
    cantDict = {}  # 存储路径对应的限制包裹ID列表

    # 遍历want数组，填充wantDict
    for arr in want:
        package, src, dst = arr  # 解构赋值：包裹ID、起始站点、目的站点
        path = f"{src}-{dst}"  # 构建路径字符串，如"A-B"
        if wantDict.get(path) is None:  # 如果路径不存在，初始化一个空列表
            wantDict[path] = [package]
        else:
            wantDict[path].append(package)  # 将包裹ID加入对应路径的列表

    # 遍历cant数组，填充cantDict
    for arr in cant:
        src = arr[0]  # 起始站点
        dst = arr[1]  # 目的站点
        path = f"{src}-{dst}"  # 构建路径字符串
        packages = arr[2:]  # 获取限制包裹ID列表
        if cantDict.get(path) is None:  # 如果路径不存在，初始化一个空列表
            cantDict[path] = packages[::]
        else:
            cantDict[path].extend(packages)  # 将限制包裹ID加入对应路径的列表

    ans = []  # 存储无法运输的包裹ID

    # 遍历wantDict中的每个路径
    for path in wantDict.keys():
        if cantDict.get(path) is None:  # 如果当前路径没有限制，跳过
            continue

        wantPKG = set(wantDict[path])  # 当前路径需要运输的包裹ID集合
        cantPKG = set(cantDict[path])  # 当前路径限制运输的包裹ID集合

        # 遍历需要运输的包裹ID
        for pkg in wantPKG:
            if pkg in cantPKG:  # 如果包裹ID在限制列表中，加入结果列表
                ans.append(pkg)

    # 如果没有无法运输的包裹，返回"none"
    if len(ans) > 0:
        ans.sort(key=lambda x: int(x[7:]))  # 对结果列表按包裹ID的数字部分排序（假设包裹ID格式为"packageX"）
        return " ".join(ans)  # 将排序后的包裹ID拼接成字符串
    else:
        return "none"


# 调用getResult函数计算结果并输出
print(getResult(want, cant))

---

代码逻辑详解

1. 输入处理：

   • 使用input().split()读取输入数据。
   • 第一行输入是m和n，分别表示包裹运输需求的条数和限制条件的条数。
   • 接下来的m行是包裹运输需求，存储在want数组中。
   • 接下来的n行是运输限制条件，存储在cant数组中。

2. 数据结构：

   • wantDict：一个字典，键是路径（如"A-B"），值是该路径需要运输的包裹ID列表。
   • cantDict：一个字典，键是路径，值是该路径限制运输的包裹ID列表。

3. 填充wantDict和cantDict：

   • 遍历want数组，将每个包裹ID加入对应路径的列表。
   • 遍历cant数组，将每个限制包裹ID加入对应路径的列表。

4. 查找无法运输的包裹：

   • 遍历wantDict中的每个路径，检查该路径需要运输的包裹ID是否在cantDict的限制列表中。
   • 如果存在限制，将包裹ID加入结果列表ans。

5. 结果处理：

   • 如果ans为空，返回"none"。
   • 否则，对ans中的包裹ID按数字部分排序（假设包裹ID格式为packageX），并拼接成字符串返回。

---

示例运行

输入：

3 2
package1 A B
package2 A C
package3 B C
A B package1 package2
B C package3

输出：

package1 package3

解释：

• 路径A-B限制运输package1和package2，但只有package1在需求列表中。
• 路径B-C限制运输package3，且package3在需求列表中。
• 最终输出无法运输的包裹ID：package1 package3。

---

总结

这段Python代码通过合理的数据结构（字典和集合）和逻辑处理，高效地解决了包裹运输问题。代码结构清晰，注释详细，适合用于需要处理大量输入并进行复杂逻辑判断的场景。

五、C/C++算法源码：

---

C++ 实现

C++ 代码

#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <algorithm>
using namespace std;

// 算法入口
string getResult(vector<vector<string>>& want, vector<vector<string>>& cant) {
    // 使用map存储路径对应的包裹ID列表
    map<string, vector<string>> wantDict; // 存储运输需求
    map<string, vector<string>> cantDict; // 存储运输限制

    // 遍历want数组，填充wantDict
    for (auto& arr : want) {
        string package = arr[0]; // 包裹ID
        string src = arr[1];     // 起始站点
        string dst = arr[2];     // 目的站点
        string path = src + "-" + dst; // 构建路径字符串，如"A-B"
        wantDict[path].push_back(package); // 将包裹ID加入对应路径的列表
    }

    // 遍历cant数组，填充cantDict
    for (auto& arr : cant) {
        string src = arr[0];     // 起始站点
        string dst = arr[1];     // 目的站点
        string path = src + "-" + dst; // 构建路径字符串
        for (int i = 2; i < arr.size(); i++) {
            cantDict[path].push_back(arr[i]); // 将限制包裹ID加入对应路径的列表
        }
    }

    vector<string> ans; // 存储无法运输的包裹ID

    // 遍历wantDict中的每个路径
    for (auto& [path, wantPKG] : wantDict) {
        if (cantDict.find(path) == cantDict.end()) continue; // 如果当前路径没有限制，跳过

        set<string> wantSet(wantPKG.begin(), wantPKG.end()); // 当前路径需要运输的包裹ID集合
        set<string> cantSet(cantDict[path].begin(), cantDict[path].end()); // 当前路径限制运输的包裹ID集合

        // 遍历需要运输的包裹ID
        for (auto& pkg : wantSet) {
            if (cantSet.find(pkg) != cantSet.end()) {
                ans.push_back(pkg); // 如果包裹ID在限制列表中，加入结果列表
            }
        }
    }

    // 如果没有无法运输的包裹，返回"none"
    if (ans.empty()) return "none";

    // 对结果列表按包裹ID的数字部分排序
    sort(ans.begin(), ans.end(), [](string& a, string& b) {
        return stoi(a.substr(7)) < stoi(b.substr(7)); // 假设包裹ID格式为"packageX"
    });

    // 将排序后的包裹ID拼接成字符串
    string result;
    for (int i = 0; i < ans.size(); i++) {
        if (i > 0) result += " ";
        result += ans[i];
    }
    return result;
}

int main() {
    int m, n;
    cin >> m >> n; // 读取m和n，分别表示包裹运输需求的条数和限制条件的条数

    vector<vector<string>> want(m); // 存储包裹运输需求
    for (int i = 0; i < m; i++) {
        string package, src, dst;
        cin >> package >> src >> dst; // 读取每行包裹运输需求
        want[i] = {package, src, dst};
    }

    vector<vector<string>> cant(n); // 存储运输限制条件
    for (int i = 0; i < n; i++) {
        string src, dst;
        cin >> src >> dst; // 读取起始站点和目的站点
        vector<string> packages;
        string package;
        while (cin >> package) { // 读取限制包裹ID列表
            packages.push_back(package);
            if (cin.get() == '\n') break; // 如果遇到换行符，结束读取
        }
        cant[i] = {src, dst};
        cant[i].insert(cant[i].end(), packages.begin(), packages.end());
    }

    // 调用getResult函数计算结果并输出
    cout << getResult(want, cant) << endl;
    return 0;
}

---

C++ 代码讲解

1. 输入处理：

   • 使用cin读取输入数据。
   • 第一行输入是m和n，分别表示包裹运输需求的条数和限制条件的条数。
   • 接下来的m行是包裹运输需求，存储在want数组中。
   • 接下来的n行是运输限制条件，存储在cant数组中。

2. 数据结构：

   • wantDict：一个map，键是路径（如"A-B"），值是该路径需要运输的包裹ID列表。
   • cantDict：一个map，键是路径，值是该路径限制运输的包裹ID列表。

3. 填充wantDict和cantDict：

   • 遍历want数组，将每个包裹ID加入对应路径的列表。
   • 遍历cant数组，将每个限制包裹ID加入对应路径的列表。

4. 查找无法运输的包裹：

   • 遍历wantDict中的每个路径，检查该路径需要运输的包裹ID是否在cantDict的限制列表中。
   • 如果存在限制，将包裹ID加入结果列表ans。

5. 结果处理：

   • 如果ans为空，返回"none"。
   • 否则，对ans中的包裹ID按数字部分排序（假设包裹ID格式为packageX），并拼接成字符串返回。

---

C 语言实现

C 代码

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX_LEN 1000

// 比较函数，用于排序
int compare(const void* a, const void* b) {
    char* pkg1 = *(char**)a;
    char* pkg2 = *(char**)b;
    int num1 = atoi(pkg1 + 7); // 提取包裹ID的数字部分
    int num2 = atoi(pkg2 + 7);
    return num1 - num2;
}

// 算法入口
char* getResult(char*** want, int m, char*** cant, int n) {
    // 使用动态数组存储路径对应的包裹ID列表
    char** wantPaths[MAX_LEN] = {0}; // 存储路径
    char*** wantDict = (char***)calloc(MAX_LEN, sizeof(char**)); // 存储运输需求
    char*** cantDict = (char***)calloc(MAX_LEN, sizeof(char**)); // 存储运输限制

    // 遍历want数组，填充wantDict
    for (int i = 0; i < m; i++) {
        char* package = want[i][0]; // 包裹ID
        char* src = want[i][1];     // 起始站点
        char* dst = want[i][2];     // 目的站点
        char path[MAX_LEN];
        sprintf(path, "%s-%s", src, dst); // 构建路径字符串，如"A-B"

        // 查找路径是否已存在
        int found = 0;
        for (int j = 0; j < MAX_LEN && wantPaths[j] != NULL; j++) {
            if (strcmp(wantPaths[j], path) == 0) {
                found = 1;
                break;
            }
        }

        // 如果路径不存在，添加到wantPaths
        if (!found) {
            for (int j = 0; j < MAX_LEN; j++) {
                if (wantPaths[j] == NULL) {
                    wantPaths[j] = strdup(path);
                    break;
                }
            }
        }

        // 将包裹ID加入对应路径的列表
        for (int j = 0; j < MAX_LEN; j++) {
            if (wantPaths[j] != NULL && strcmp(wantPaths[j], path) == 0) {
                if (wantDict[j] == NULL) {
                    wantDict[j] = (char**)calloc(MAX_LEN, sizeof(char*));
                }
                for (int k = 0; k < MAX_LEN; k++) {
                    if (wantDict[j][k] == NULL) {
                        wantDict[j][k] = strdup(package);
                        break;
                    }
                }
                break;
            }
        }
    }

    // 遍历cant数组，填充cantDict
    for (int i = 0; i < n; i++) {
        char* src = cant[i][0];     // 起始站点
        char* dst = cant[i][1];     // 目的站点
        char path[MAX_LEN];
        sprintf(path, "%s-%s", src, dst); // 构建路径字符串

        // 查找路径是否已存在
        int found = 0;
        for (int j = 0; j < MAX_LEN && wantPaths[j] != NULL; j++) {
            if (strcmp(wantPaths[j], path) == 0) {
                found = 1;
                break;
            }
        }

        // 如果路径不存在，跳过
        if (!found) continue;

        // 将限制包裹ID加入对应路径的列表
        for (int j = 0; j < MAX_LEN; j++) {
            if (wantPaths[j] != NULL && strcmp(wantPaths[j], path) == 0) {
                if (cantDict[j] == NULL) {
                    cantDict[j] = (char**)calloc(MAX_LEN, sizeof(char*));
                }
                for (int k = 2; k < MAX_LEN && cant[i][k] != NULL; k++) {
                    cantDict[j][k - 2] = strdup(cant[i][k]);
                }
                break;
            }
        }
    }

    char** ans = (char**)calloc(MAX_LEN, sizeof(char*)); // 存储无法运输的包裹ID
    int ansCount = 0;

    // 遍历wantDict中的每个路径
    for (int i = 0; i < MAX_LEN && wantPaths[i] != NULL; i++) {
        if (cantDict[i] == NULL) continue; // 如果当前路径没有限制，跳过

        // 遍历需要运输的包裹ID
        for (int j = 0; j < MAX_LEN && wantDict[i][j] != NULL; j++) {
            char* pkg = wantDict[i][j];
            // 检查包裹ID是否在限制列表中
            for (int k = 0; k < MAX_LEN && cantDict[i][k] != NULL; k++) {
                if (strcmp(pkg, cantDict[i][k]) == 0) {
                    ans[ansCount++] = strdup(pkg); // 如果包裹ID在限制列表中，加入结果列表
                    break;
                }
            }
        }
    }

    // 如果没有无法运输的包裹，返回"none"
    if (ansCount == 0) return "none";

    // 对结果列表按包裹ID的数字部分排序
    qsort(ans, ansCount, sizeof(char*), compare);

    // 将排序后的包裹ID拼接成字符串
    char* result = (char*)calloc(MAX_LEN, sizeof(char));
    for (int i = 0; i < ansCount; i++) {
        if (i > 0) strcat(result, " ");
        strcat(result, ans[i]);
    }

    // 释放动态分配的内存
    for (int i = 0; i < MAX_LEN; i++) {
        if (wantDict[i] != NULL) {
            for (int j = 0; j < MAX_LEN && wantDict[i][j] != NULL; j++) {
                free(wantDict[i][j]);
            }
            free(wantDict[i]);
        }
        if (cantDict[i] != NULL) {
            for (int j = 0; j < MAX_LEN && cantDict[i][j] != NULL; j++) {
                free(cantDict[i][j]);
            }
            free(cantDict[i]);
        }
    }
    free(wantDict);
    free(cantDict);

    return result;
}

int main() {
    int m, n;
    scanf("%d %d", &m, &n); // 读取m和n，分别表示包裹运输需求的条数和限制条件的条数

    char*** want = (char***)malloc(m * sizeof(char**)); // 存储包裹运输需求
    for (int i = 0; i < m; i++) {
        want[i] = (char**)malloc(3 * sizeof(char*));
        want[i][0] = (char*)malloc(MAX_LEN * sizeof(char));
        want[i][1] = (char*)malloc(MAX_LEN * sizeof(char));
        want[i][2] = (char*)malloc(MAX_LEN * sizeof(char));
        scanf("%s %s %s", want[i][0], want[i][1], want[i][2]); // 读取每行包裹运输需求
    }

    char*** cant = (char***)malloc(n * sizeof(char**)); // 存储运输限制条件
    for (int i = 0; i < n; i++) {
        cant[i] = (char**)malloc(MAX_LEN * sizeof(char*));
        cant[i][0] = (char*)malloc(MAX_LEN * sizeof(char));
        cant[i][1] = (char*)malloc(MAX_LEN * sizeof(char));
        scanf("%s %s", cant[i][0], cant[i][1]); // 读取起始站点和目的站点
        int j = 2;
        while (1) {
            cant[i][j] = (char*)malloc(MAX_LEN * sizeof(char));
            if (scanf("%s", cant[i][j]) != 1) break; // 读取限制包裹ID列表
            j++;
        }
    }

    // 调用getResult函数计算结果并输出
    char* result = getResult(want, m, cant, n);
    printf("%s\n", result);

    // 释放动态分配的内存
    for (int i = 0; i < m; i++) {
        free(want[i][0]);
        free(want[i][1]);
        free(want[i][2]);
        free(want[i]);
    }
    free(want);

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < MAX_LEN && cant[i][j] != NULL; j++) {
            free(cant[i][j]);
        }
        free(cant[i]);
    }
    free(cant);

    free(result);
    return 0;
}

---

C 代码讲解

1. 输入处理：

   • 使用scanf读取输入数据。
   • 第一行输入是m和n，分别表示包裹运输需求的条数和限制条件的条数。
   • 接下来的m行是包裹运输需求，存储在want数组中。
   • 接下来的n行是运输限制条件，存储在cant数组中。

2. 数据结构：

   • 使用动态数组和字符串指针来模拟字典和列表的功能。

3. 填充wantDict和cantDict：

   • 遍历want数组，将每个包裹ID加入对应路径的列表。
   • 遍历cant数组，将每个限制包裹ID加入对应路径的列表。

4. 查找无法运输的包裹：

   • 遍历wantDict中的每个路径，检查该路径需要运输的包裹ID是否在cantDict的限制列表中。
   • 如果存在限制，将包裹ID加入结果列表ans。

5. 结果处理：

   • 如果ans为空，返回"none"。
   • 否则，对ans中的包裹ID按数字部分排序（假设包裹ID格式为packageX），并拼接成字符串返回。

---

总结

C++和C语言的实现都通过合理的数据结构和逻辑处理，高效地解决了包裹运输问题。C++版本利用了STL库的便利性，而C语言版本则通过动态数组和字符串指针实现了类似的功能。两种实现都适合用于需要处理大量输入并进行复杂逻辑判断的场景。

六、尾言

什么是华为OD？

华为OD（Outsourcing Developer，外包开发工程师）是华为针对软件开发工程师岗位的一种招聘形式，主要包括笔试、技术面试以及综合面试等环节。尤其在笔试部分，算法题的机试至关重要。

为什么刷题很重要？

1. 机试是进入技术面的第一关：
   华为OD机试（常被称为机考）主要考察算法和编程能力。只有通过机试，才能进入后续的技术面试环节。

2. 技术面试需要手撕代码：
   技术一面和二面通常会涉及现场编写代码或算法题。面试官会注重考察候选人的思路清晰度、代码规范性以及解决问题的能力。因此提前刷题、多练习是通过面试的重要保障。

3. 入职后的可信考试：
   入职华为后，还需要通过“可信考试”。可信考试分为三个等级：

   • 入门级：主要考察基础算法与编程能力。
   • 工作级：更贴近实际业务需求，可能涉及复杂的算法或与工作内容相关的场景题目。
   • 专业级：最高等级，考察深层次的算法以及优化能力，与薪资直接挂钩。

刷题策略与说明：

2024年8月14日之后，华为OD机试的题库转为 E卷，由往年题库（D卷、A卷、B卷、C卷）和全新题目组成。刷题时可以参考以下策略：

1. 关注历年真题：

   • 题库中的旧题占比较大，建议优先刷历年的A卷、B卷、C卷、D卷题目。
   • 对于每道题目，建议深度理解其解题思路、代码实现，以及相关算法的适用场景。

2. 适应新题目：

   • E卷中包含全新题目，需要掌握全面的算法知识和一定的灵活应对能力。
   • 建议关注新的刷题平台或交流群，获取最新题目的解析和动态。

3. 掌握常见算法：
   华为OD考试通常涉及以下算法和数据结构：

   • 排序算法（快速排序、归并排序等）
   • 动态规划（背包问题、最长公共子序列等）
   • 贪心算法
   • 栈、队列、链表的操作
   • 图论（最短路径、最小生成树等）
   • 滑动窗口、双指针算法

4. 保持编程规范：

   • 注重代码的可读性和注释的清晰度。
   • 熟练使用常见编程语言，如C++、Java、Python等。

如何获取资源？

1. 官方参考：

   • 华为招聘官网或相关的招聘平台会有一些参考信息。
   • 华为OD的相关公众号可能也会发布相关的刷题资料或学习资源。

2. 加入刷题社区：

   • 找到可信的刷题交流群，与其他备考的小伙伴交流经验。
   • 关注知名的刷题网站，如LeetCode、牛客网等，这些平台上有许多华为OD的历年真题和解析。

3. 寻找系统性的教程：

   • 学习一本经典的算法书籍，例如《算法导论》《剑指Offer》《编程之美》等。
   • 完成系统的学习课程，例如数据结构与算法的在线课程。

积极心态与持续努力：

刷题的过程可能会比较枯燥，但它能够显著提升编程能力和算法思维。无论是为了通过华为OD的招聘考试，还是为了未来的职业发展，这些积累都会成为重要的财富。

考试注意细节

1. 本地编写代码

   • 在本地 IDE（如 VS Code、PyCharm 等）上编写、保存和调试代码，确保逻辑正确后再复制粘贴到考试页面。这样可以减少语法错误，提高代码准确性。

2. 调整心态，保持冷静

   • 遇到提示不足或实现不确定的问题时，不必慌张，可以采用更简单或更有把握的方法替代，确保思路清晰。

3. 输入输出完整性

   • 注意训练和考试时都需要编写完整的输入输出代码，尤其是和题目示例保持一致。完成代码后务必及时调试，确保功能符合要求。

4. 快捷键使用

   • 删除行可用 Ctrl+D，复制、粘贴和撤销分别为 Ctrl+C，Ctrl+V，Ctrl+Z，这些可以正常使用。
   • 避免使用 Ctrl+S，以免触发浏览器的保存功能。

5. 浏览器要求

   • 使用最新版的 Google Chrome 浏览器完成考试，确保摄像头开启并正常工作。考试期间不要切换到其他网站，以免影响考试成绩。

6. 交卷相关

   • 答题前，务必仔细查看题目示例，避免遗漏要求。
   • 每完成一道题后，点击【保存并调试】按钮，多次保存和调试是允许的，系统会记录得分最高的一次结果。完成所有题目后，点击【提交本题型】按钮。
   • 确保在考试结束前提交试卷，避免因未保存或调试失误而丢分。

7. 时间和分数安排

   • 总时间：150 分钟；总分：400 分。
   • 试卷结构：2 道一星难度题（每题 100 分），1 道二星难度题（200 分）。及格分为 150 分。合理分配时间，优先完成自己擅长的题目。

8. 考试环境准备

   • 考试前请备好草稿纸和笔。考试中尽量避免离开座位，确保监控画面正常。
   • 如需上厕所，请提前规划好时间以减少中途离开监控的可能性。

9. 技术问题处理

   • 如果考试中遇到断电、断网、死机等技术问题，可以关闭浏览器并重新打开试卷链接继续作答。
   • 出现其他问题，请第一时间联系 HR 或监考人员进行反馈。

祝你考试顺利，取得理想成绩！