✅ 秋招备战指南 ✅

💡 学习建议：

• 先尝试独立解题
• 对照解析查漏补缺

🧸 题面描述背景等均已深度改编，做法和题目本质基本保持一致。

🍹 感谢各位朋友们的订阅，你们的支持是我们创作的最大动力

🌸 目前本专栏已经上线100+套真题改编解析，后续会持续更新的

春秋招笔试机考招合集 -> 互联网必备刷题宝典🔗

题目一：艺术品拍卖会

1️⃣：使用有序集合分别维护不同风格的艺术品，按估价编号排序

2️⃣：每位收藏家选择偏好风格中编号最小的艺术品，竞拍后从相关集合中删除

难度：中等

这道题目的关键在于高效地维护和查询符合条件的艺术品。通过为每种风格标签建立有序集合，可以快速找到估价编号最小的艺术品，避免了暴力枚举的时间复杂度问题。

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

1️⃣：检查配置中的线路是否满足匹配条件（不共享基站）

2️⃣：检查其他线路是否满足独立条件（最多与配置共享一个基站）

3️⃣：使用布尔数组快速标记和查询基站的占用状态

难度：中等

这道题目结合了图论中独立匹配的概念，需要理解匹配和独立两个条件的含义。通过分步检查这两个条件，可以准确判断给定的线路配置是否符合高质量通信配置的标准。

01. 艺术品拍卖会

问题描述

小兰经营着一家知名的艺术品拍卖行，目前有 件艺术品待拍卖。每件艺术品都有两个重要的艺术风格标签，第 件艺术品的第一个风格标签为 ，第二个风格标签为 。根据艺术品的历史价值和稀有程度，拍卖行为每件艺术品分配了唯一的"估价编号" ，编号越小代表估价越高，也就是拍卖优先级越高。

今天拍卖会正式开始，共有 位收藏家按顺序参与竞拍。每位收藏家都专注于某个特定的艺术风格，第 位收藏家偏好的风格标签为 。收藏家只会竞拍那些第一个风格标签或第二个风格标签中至少有一个是他们偏好风格的艺术品。如果当前还有符合收藏家偏好的艺术品，他会选择其中估价编号最小（价值最高）的那件艺术品进行竞拍并成功获得。竞拍成功后（或者选择放弃），下一位收藏家才开始竞拍。如果没有心仪的艺术品（或拍卖会已经结束）则会放弃竞拍。

输入格式

第一行包含一个正整数 ，表示艺术品的数量。

第二行包含 个正整数，第 个数 表示第 件艺术品的估价编号。

第三行包含 个正整数，第 个数 表示第 件艺术品的第一个风格标签。

第四行包含 个正整数，第 个数 表示第 件艺术品的第二个风格标签。

第五行包含一个正整数 ，表示收藏家的数量。

第六行包含 个正整数，第 个数 表示第 位收藏家偏好的风格标签。

输出格式

输出一行包含 个数，第 个数表示第 位收藏家竞拍到的艺术品的估价编号，如果第 位收藏家没有竞拍到任何艺术品，则输出 。

样例输入

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

样例输出

5 10 25 40 -1

数据范围

题解

这道题的核心是模拟拍卖过程，关键在于高效地维护和查询符合条件的艺术品。

首先分析问题：每位收藏家需要在剩余的艺术品中找到风格标签匹配且估价编号最小的艺术品。如果每次都遍历所有剩余艺术品，时间复杂度会达到 ，在最坏情况下可能超时。

更好的方法是使用数据结构来维护不同风格的艺术品。我们可以为每种风格标签建立一个集合，集合中存储该风格对应的艺术品，并按估价编号从小到大排序。

具体实现思路：

1. 读入所有艺术品信息后，为每种风格标签创建一个有序集合
2. 遍历每件艺术品，将其加入到对应风格标签的集合中
3. 对于每位收藏家，在其偏好风格的集合中找到估价编号最小的艺术品
4. 成功竞拍后，需要将该艺术品从所有相关的风格集合中删除

需要注意的是，一件艺术品可能有两个不同的风格标签，需要同时加入两个集合；删除时也要从所有包含该艺术品的集合中移除。

时间复杂度分析：建立集合需要 ，每次查询和删除操作需要 ，总时间复杂度为 ，对于给定的数据范围完全可以接受。

参考代码

Python

import sys
input = lambda: sys.stdin.readline().strip()

n = int(input())
x = list(map(int, input().split()))
a = list(map(int, input().split()))
b = list(map(int, input().split()))
m = int(input())
c = list(map(int, input().split()))

# 为每种风格创建有序列表，存储(估价编号, 艺术品索引)
style_sets = [[] for _ in range(4)]

# 将艺术品按风格分类并排序
for i in range(n):
    style_sets[a[i]].append((x[i], i))
    if b[i] != a[i]:  # 避免重复添加相同风格
        style_sets[b[i]].append((x[i], i))

# 对每个风格的艺术品按估价编号排序
for i in range(4):
    style_sets[i].sort()

# 标记艺术品是否已被竞拍
sold = [False] * n
ans = []

for i in range(m):
    fav_style = c[i]
    found = False
    
    # 在偏好风格中找到估价最小且未被竞拍的艺术品
    for j, (price, idx) in enumerate(style_sets[fav_style]):
        if not sold[idx]:
            ans.append(price)
            sold[idx] = True  # 标记为已竞拍
            found = True
            break
    
    if not found:
        ans.append(-1)

print(' '.join(map(str, ans)))

Cpp

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n;
    cin >> n;
    vector<int> x(n), a(n), b(n);
    
    // 读入艺术品信息
    for (int i = 0; i < n; i++) cin >> x[i];
    for (int i = 0; i < n; i++) cin >> a[i];
    for (int i = 0; i < n; i++) cin >> b[i];
    
    int m;
    cin >> m;
    vector<int> c(m);
    for (int i = 0; i < m; i++) cin >> c[i];
    
    // 为每种风格创建有序集合
    vector<set<pair<int, int>>> style_map(4);
    for (int i = 0; i < n; i++) {
        style_map[a[i]].insert({x[i], i});
        if (b[i] != a[i]) {
            style_map[b[i]].insert({x[i], i});
        }
    }
    
    vector<int> ans(m, -1);
    for (int i = 0; i < m; i++) {
        int fav = c[i];
        if (!style_map[fav].empty()) {
            auto it = style_map[fav].begin();
            int art_idx = it->second;
            ans[i] = it->first;
            
            // 从所有相关集合中删除该艺术品
            style_map[a[art_idx]].erase({x[art_idx], art_idx});
            if (b[art_idx] != a[art_idx]) {
                style_map[b[art_idx]].erase({x[art_idx], art_idx});
            }
        }
    }
    
    // 输出结果
    for (int i = 0; i < m; i++) {
        cout << ans[i] << (i + 1 < m ? ' ' : '\n');
    }
    
    return 0;
}

Java

import java.util.*;
import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        
        int n = Integer.parseInt(br.readLine());
        int[] x = new int[n], a = new int[n], b = new int[n];
        
        // 读入艺术品信息
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) {
            x[i] = Integer.parseInt(st.nextToken());
        }
        
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) {
            a[i] = Integer.parseInt(st.nextToken());
        }
        
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) {
            b[i] = Integer.parseInt(st.nextToken());
        }
        
        int m = Integer.parseInt(br.readLine());
        int[] c = new int[m];
        st = new StringTokenizer(br.readLine());
        for