热乎乎的京东笔试复盘（07.26场）：两道编程题思路与踩坑点

哈喽，牛友们！

上周京东最新的笔试，感觉被好好“教育”了一番。今天终于有空，把两道印象深刻的编程题从头到尾复盘了一下，把详细的思路、解法和一些容易踩的坑整理出来，希望能给后面参加秋招的同学提供一点有价值的参考。

总体感觉今年京东的题很有水平，非常考验咱们数据结构的基本功和对问题建模、分解的能力。废话不多说，我们直接上干货！

第一题：艺术品拍卖会

1. 题目大意

简单来说，这是一个拍卖模拟题。有 n 件艺术品，每件都有唯一的估价编号（越小越好）和两个风格标签。然后有 m 个收藏家按顺序来买东西，每个收藏家只喜欢某一种特定风格。轮到他时，他会从所有符合他偏好风格、且还没被卖掉的艺术品中，选那个估价编号最小的买走。我们需要输出每个收藏家最终买到的艺术品编号，没买到就输出-1。

2. 考点分析

这道题的核心是**“动态查询最小值”**。

因为艺术品被买走后就不能再被选择，所以数据是动态变化的。如果每次都暴力遍历所有艺术品来找最小值，在 n 和 m 的数据量下肯定会超时。所以，这题考察的是我们能否选用一个高效的数据结构来维护和查询。正确答案是使用有序集合，在C++里是 std::set，Java里是 TreeSet，Python中可以用 heapq (小顶堆) 来高效实现。

3. 样例输入与输出

样例输入

4
25 10 5 40
1 2 3 1
3 1 2 2
5
2 1 3 2 1

样例输出

5 10 25 40 -1

4. 解题思路

我们的目标是快速找到每个风格中“现存的、编号最小的”艺术品。

1. 数据预处理： 使用一个字典或哈希表（比如 style_map），key 是风格编号 (1, 2, 3)，value 是一个数据结构，用来存放所有包含该风格的艺术品信息 (估价编号, 艺术品原始索引)。

2. 选择数据结构： 为了快速取最小值，这个数据结构最好是小顶堆。我们将所有艺术品按它们的风格标签，分别放入对应的小顶堆里。一件艺术品有两个风格，就入两个堆。

3. 模拟拍卖： 遍历每个收藏家。

   • 根据其偏好风格 c，找到对应的堆 style_map[c]。

   • 关键一步： 堆顶的艺术品不一定是能买的，因为它可能已经被别的收藏家（通过另一个风格）买走了。所以我们需要一个 sold 数组来标记艺术品是否已售出。

   • 循环查看堆顶元素，如果堆不为空且堆顶的艺术品已被标记为 sold，就 heappop 弹出，直到堆顶是一个未售出的艺术品，或者堆为空。这种“懒删除”的技巧（用sold标记而不是真的从所有相关堆里删除）非常实用。

   • 如果堆为空，说明没得买，记录-1。

   • 如果堆不为空，就成功找到了目标。记录下估价编号，并把该艺术品的 sold 标记为 true。

5. AC代码 (Python)

Python

import sys
import heapq

def solve():
    """
    艺术品拍卖会问题求解函数
    """
    # 使用 sys.stdin.readline 以提高I/O效率
    input = sys.stdin.readline

    # 1. 数据读入
    n = int(input())
    prices = list(map(int, input().split()))
    styles_a = list(map(int, input().split()))
    styles_b = list(map(int, input().split()))
    m = int(input())
    collectors = list(map(int, input().split()))

    # 2. 数据预处理：为每种风格创建一个小顶堆
    # style_heaps 的 key 是风格编号，value 是一个小顶堆
    # 堆中存放元组 (price, original_index)
    style_heaps = {1: [], 2: [], 3: []}
    
    # 艺术品信息存入对应风格的堆中
    for i in range(n):
        price = prices[i]
        style1 = styles_a[i]
        style2 = styles_b[i]
        
        heapq.heappush(style_heaps[style1], (price, i))
        if style1 != style2:
            heapq.heappush(style_heaps[style2], (price, i))

    # 3. 模拟拍卖过程
    # 使用布尔数组标记艺术品是否已售出
    sold = [False] * n
    results = []

    for fav_style in collectors:
        target_price = -1
        
        # 核心逻辑：懒删除
        # 循环查看堆顶，如果艺术品已售出，则弹出，直到找到未售出的或堆为空
        heap = style_heaps.get(fav_style, [])
        while heap and sold[heap[0][1]]:
            heapq.heappop(heap)

        # 如果堆不为空，说明找到了可以购买的艺术品
        if heap:
            price, index = heap[0]
            target_price = price
            sold[index] = True
        
        results.append(target_price)

    # 4. 输出结果
    print(' '.join(map(str, results)))

solve()

第二题：通信网络质量检测

1. 题目大意

这题是判断一个给定的“线路配置方案”是否“高质量”。高质量需要同时满足两个条件：

1. 独占性： 方案里的线路，两两之间不能有公共的基站（端点）。这其实就是图论里**“匹配 (Matching)”**的定义。

2. 低干扰性： 不在方案里的任何一条“外部线路”，它最多只能和方案里的所有线路共享一个基站。

我们需要对 q 个给定的方案，逐一判断输出 "Yes" 或 "No"。

2. 考点分析

这道题的本质是图论概念的理解和模拟。

不需要用到复杂的图算法，但需要准确理解“匹配”和题目自定义的“低干扰”这两个概念。解题的关键在于如何高效地检查这两个条件，正确答案是使用布尔数组（或哈希表）来标记基站的占用状态。

3. 样例输入与输出

样例输入

6 6
1 2 3 4 5 6
2 3 4 5 6 1
3
2 1 2
2 2 4
2 3 6

样例输出

No
No
Yes

4. 解题思路

对于每一个查询，我们都需要独立地进行一次完整的检查。

1. 初始化： 对于每个查询，都需要一个全新的 is_station_occupied 布尔数组（标记基站是否被方案内线路占用）和一个 is_in_config 布尔数组（标记某条线路ID是否在当前方案内）。

2. 步骤一：检查独占性 (匹配条件)

   • 遍历方案中的每条线路。

   • 对于每条线路的两个基站端点，检查 is_station_occupied。如果任意一个端点已经是 true，说明有共享，独占性被违反，直接判定为 "No"，结束当前查询。

   • 如果两个端点都没被占用，就把它们在 is_station_occupied 中标记为 true。

3. 步骤二：检查低干扰性

   • 只有在步骤一完全通过后，才进行此步骤。

   • 遍历从1到 m 的所有线路。如果某条线路在当前配置方案内 (is_in_config 为 true)，就跳过。

   • 对于每条“外部线路”，检查它的两个端点。统计有几个端点在 is_station_occupied 中为 true。

   • 如果统计结果大于1，说明低干扰性被违反，直接判定为 "No"，结束当前查询。

4. 最终判断： 如果所有检查都顺利通过，那么方案是高质量的，输出 "Yes"。

5. AC代码 (Python)

Python

import sys

def solve():
    """
    通信网络质量检测问题求解函数
    """
    input = sys.stdin.readline

    # 1. 读入网络基础信息
    n, m = map(int, input().split())
    # 线路端点信息，使用 1-based index
    endpoints_u = [0] + list(map(int, input().split()))
    endpoints_v = [0] + list(map(int, input().split()))

    # 2. 处理q个查询
    q = int(input())
    for _ in range(q):
        query_data = list(map(int, input().split()))
        # config_edges 是当前方案包含的线路ID列表
        config_edges = query_data[1:]
        
        is_valid = True
        
        # --- 步骤一：检查独占性 (匹配条件) ---
        is_station_occupied = [False] * (n + 1)
        
        for edge_id in config_edges:
            u, v = endpoints_u[edge_id], endpoints_v[edge_id]
            # 如果任一端点已被占用，则违反独占性
            if is_station_occupied[u] or is_station_occupied[v]:
                is_valid = False
                break
            # 标记端点为已占用
            is_station_occupied[u] = True
            is_station_occupied[v] = True
        
        if not is_valid:
            print("No")
            continue

        # --- 步骤二：检查低干扰性 ---
        # 标记哪些线路在配置方案中，以便快速跳过
        is_in_config = [False] * (m + 1)
        for edge_id in config_edges:
            is_in_config[edge_id] = True

        for i in range(1, m + 1):
            # 只检查不在配置方案内的“外部线路”
            if not is_in_config[i]:
                u, v = endpoints_u[i], endpoints_v[i]
                shared_count = 0
                if is_station_occupied[u]:
                    shared_count += 1
                if is_station_occupied[v]:
                    shared_count += 1
                
                # 如果共享基站超过1个，则违反低干扰性
                if shared_count > 1:
                    is_valid = False
                    break
        
        if not is_valid:
            print("No")
            continue
            
        # 3. 如果所有检查都通过
        print("Yes")

solve()

总结

这次复盘就到这里啦。总的来说，京东的这两道题虽然没有用上什么非常高级的算法，但都精准地打在了“知不知道该用什么数据结构”和“能不能清晰地分析问题”这两个点上。希望我的思路和代码能给大家带来一些启发。

秋招是场硬仗，我们一起加油，祝大家都能拿到心仪的Offer！