🍭 大家好这里是 春秋招笔试突围，一起备战大厂笔试

💻 ACM金牌团队🏅️ | 多次AK大厂笔试 ｜ 大厂实习经历

✨ 本系列打算持续跟新 春秋招笔试题

👏 感谢大家的订阅➕ 和 喜欢💗 和 手里的小花花🌸

✨ 笔试合集传送们 -> 🧷学长刷题笔记

🍒 本专栏已收集 100+ 套笔试题，笔试真题 会在第一时间跟新

🍄 题面描述等均已改编，如果和你笔试题看到的题面描述不一样请理解，做法和题目本质基本不变。

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

🌈 秋招笔试，来啦！！！

🧸 本次的T2为 1016 版的 T3 原题哦～

1️⃣ 模拟+贪心+自定义排序

2️⃣ 思维+贪心+分类讨论

3️⃣ 状态压缩 BFS，当然也可以用状压DP的方式实现。

🍴 01.餐厅套餐优化问题 评测链接🔗

问题描述

LYA 餐厅为了提升销售额，推出了多种套餐组合。每个套餐都包含一个主食和若干配菜或饮品。例如：

• 套餐A：牛肉汉堡 + 薯条 + 可乐
• 套餐B：鸡肉卷 + 玉米汤 + 冰淇淋
• 套餐C：意大利面 + 沙拉 + 柠檬水

为了即将到来的店庆活动，餐厅需要从现有套餐中选择部分进行促销。选择时需要考虑以下因素：

1. 每个套餐都有固定的主食、成本和利润。
2. 某些主食的供应量有限制。
3. 配菜和饮品不受限制。
4. 套餐选择需遵循以下优先级：
   • 优先选择成本低的套餐
   • 成本相同时，优先选择利润高的
   • 成本和利润都相同时，优先选择编号小的套餐

请帮助餐厅在满足限制条件的情况下，选择指定数量的套餐。

输入格式

第一行一个整数 ，表示现有套餐的总数。

接下来 行，每行包含三个整数，分别表示套餐的主食编号、成本和利润。

接下来一行一个整数 ，表示有供应限制的主食数量。

接下来 行，每行两个整数，分别表示主食编号和其对应的供应上限。

最后一行一个整数 ，表示需要选择的套餐数量。

输出格式

如果能选出指定数量的套餐，输出这些套餐的编号（从小到大排序）；否则输出 。

样例输入1

6
100 30 10
200 10 10
100 50 20
200 10 10
400 20 20
200 20 10
3 
100 1
200 1
400 2
3

样例输出1

0 1 4

样例输入2

3
100 30 10 
200 10 10
100 50 20
2
100 1
200 1
3

样例输出2

-1

样例解释

样例 解释说明

样例1	共有6种套餐，需要选择3种。按照成本排序后，先选择成本为10的套餐1，由于主食200限制为1份，所以不能选择套餐3。然后选择成本为20的套餐4，最后选择成本为30的套餐0。
样例2	由于主食100和200都只能选择1份，而需要选择3种套餐，所以无法满足要求。

数据范围

• 
• 
• 
• 主食编号、成本、利润的取值范围均为

题解

模拟+贪心+自定义排序

主要思路如下：

1. 需要对所有套餐按照题目给定的优先级进行排序：
   • 成本低的优先
   • 成本相同时，利润高的优先
   • 成本和利润都相同时，编号小的优先
2. 排序后，从前往后遍历排好序的套餐：
   • 对于每个套餐，检查其主食是否超过限制
   • 如果没有超过限制或该主食无限制，则选择该套餐
   • 记录已选择的主食数量

时间复杂度分析：

• 排序需要
• 遍历套餐需要
• 总体复杂度为

关键点在于使用哈希表（或数组）来记录每种主食的使用情况，这样可以在 时间内判断是否可以选择某个套餐。

参考代码

• Python

def solve():
    # 读取套餐总数
    M = int(input())
    # 存储套餐信息
    sets = []
    for i in range(M):
        main_id, cost, profit = map(int, input().split())
        sets.append([i, main_id, cost, profit])
    
    # 读取主食限制
    N = int(input())
    limits = {}  # 存储主食限制
    for _ in range(N):
        main_id, limit = map(int, input().split())
        limits[main_id] = limit
    
    # 读取需要选择的套餐数量
    NUM = int(input())
    
    # 按照要求排序
    sets.sort(key=lambda x: (x[2], -x[3], x[0]))
    
    selected = []  # 已选择的套餐
    used = {}  # 记录主食使用次数
    
    # 遍历排序后的套餐
    for idx, main_id, cost, profit in sets:
        # 检查主食限制
        if main_id not in limits or used.get(main_id, 0) < limits[main_id]:
            selected.append(idx)
            used[main_id] = used.get(main_id, 0) + 1
            if len(selected) == NUM:
                break
    
    # 输出结果
    if len(selected) == NUM:
        print(*sorted(selected))
    else:
        print(-1)

solve()

• Java

import java.util.*;

public class Main {
    static class Set {
        int index, mainId, cost, profit;
        Set(int i, int m, int c, int p) {
            index = i;
            mainId = m;
            cost = c;
            profit = p;
        }
    }
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        // 读取套餐数量
        int M = sc.nextInt();
        List<Set> sets = new ArrayList<>();
        
        // 读取套餐信息
        for (int i = 0; i < M; i++) {
            sets.add(new Set(i, sc.nextInt(), sc.nextInt(), sc.nextInt()));
        }
        
        // 读取主食限制
        int N = sc.nextInt();
        Map<Integer, Integer> limits = new HashMap<>();
        for (int i = 0; i < N; i++) {
            limits.put(sc.nextInt(), sc.nextInt());
        }
        
        int NUM = sc.nextInt();
        
        // 排序
        Collections.sort(sets, (a, b) -> {
            if (a.cost != b.cost) return a.cost - b.cost;
            if (a.profit != b.profit) return b.profit - a.profit;
            return a.index - b.index;
        });
        
        List<Integer> selected = new ArrayList<>();
        Map<Integer, Integer> used = new HashMap<>();
        
        // 选择套餐
        for (Set s : sets) {
            int currentUse = used.getOrDefault(s.mainId, 0);
            Integer limit = limits.get(s.mainId);
            if (limit == null || currentUse < limit) {
                selected.add(s.index);
                used.put(s.mainId, currentUse + 1);
                if (selected.size() == NUM) break;
            }
        }
        
        // 输出结果
        if (selected.size() == NUM) {
            Collections.sort(selected);
            for (int i = 0; i < selected.size(); i++) {
                System.out.print(selected.get(i));
                if (i < selected.size() - 1) System.out.print(" ");
            }
        } else {
            System.out.println(-1);
        }
    }
}

• Cpp

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

// 套餐结构体
struct Set {
    int index;      // 套餐编号
    int main_id;    // 主食编号
    int cost;       // 成本
    int profit;     // 利润
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    // 读取套餐数量
    int M;
    cin >> M;
    vector<Set> sets(M);
    
    // 读取每个套餐信息
    for(int i = 0; i < M; i++) {
        cin >> sets[i].main_id >> sets[i].cost >> sets[i].profit;
        sets[i].index = i;
    }
    
    // 读取主食限制
    int N;
    cin >> N;
    const int MAX_ID = 10000;
    vector<int> limits(MAX_ID + 1, -1);  // -1表示无限制
    for(int i = 0; i < N; i++) {
        int id, lim;
        cin >> id >> lim;
        limits[id] = lim;
    }
    
    int NUM;
    cin >> NUM;
    
    // 按照要求排序
    sort(sets.begin(), sets.end(), [](const Set &a, const Set &b) {
        if(a.cost != b.cost) return a.cost < b.cost;
        if(a.profit != b.profit) return a.profit > b.profit;
        return a.index < b.index;
    });
    
    // 记录已选择的主食数量
    vector<int> selected_counts(MAX_ID + 1, 0);
    vector<int> selected_indices;
    
    // 选择套餐
    for(const auto &s: sets) {
        int main_id = s.main_id;
        if(limits[main_id] == -1 || selected_counts[main_id] < limits[main_id]) {
            selected_indices.push_back(s.index);
            if(limits[main_id] != -1) {
                selected_counts[main_id]++;
            }
            if(selected_indices.size() == NUM) {
                break;
            }
        }
    }
    
    // 输出结果
    if(selected_indices.size() == NUM) {
        sort(selected_indices.begin(), selected_indices.end());
        for(int i = 0; i < selected_indices.size(); i++) {
            if(i > 0) cout << ' ';
            cout << selected_indices[i];
        }
        cout << '\n';
    } else {
        cout << "-1\n";
    }
    return 0;
}

✨ 02.K小姐的交换魔法 评测链接🔗

问题描述

在魔法世界中，K小姐是一位著名的魔法师。她最近发明了一种新的交换魔法，可以交换两个魔法物品的位置。然而，这种魔法有一个特殊的规则：交换的代价等于两个物品位置索引的和。

K小姐有两排魔法物品，每排都有 个。她想要通过使用交换魔法，使得两排中相同位置的物品都不相同。但是，她只能对第二排的物品使用交换魔法。

你能帮助K小姐计算出达成目标所需的最小魔法代价吗？如果无法达成目标，请返回 。

输入格式

第一行输入一个整数 ，表示每排魔法物品的数量。

第二行输入 个整数，表示第一排魔法物品的编号。

第三行输入 个整数，表示第二排魔法物品的编号。

输出格式

输出一个整数，表示达成目标的最小魔法代价。如果无法达成目标，输出 。

样例输入1

4
1 2 3 4
1 2 3 4

样例输出1

6

样例输入2

3
2 1 1
1 1 2

样例输出2

-1

样例解释

样例 输入 输出 说明

样例1	4 1 2 3 4 1 2 3 4	6	一种最小代价的方法是： 1. 交换第二排中索引为0和1的物品，代价为0+1=1 2. 交换第二排中索引为2和3的物品，代价为2+3=5 总代价为1+5=6
样例2	3 2 1 1 1 1 2	-1	无论如何交换，都无法使两排相同位置的物品都不同，因此返回-1

数据范围

• 
• 魔法物品编号

题解

思维+结论/分类讨论

1. 统计相同位置
   • 遍历数组，找出所有相同位置的数字
   • 记录这些位置的下标和（作为代价）
   • 统计每个数字出现的次数
2. 找出众数
   • 在相同位置的数字中找出出现最多的数字
   • 众数的出现次数很关键，因为它决定了是否有解
3. 判断是否可行
   • 如果众数的出现次数小于等于总数的一半，则两两不同的交换即可
   • 如果众数出现次数超过总数的一半，就需要额外的交换
   • 通过第二次遍历，将众数与其他值不同的位置交换
   • 如果最终众数出现次数仍超过一半，则无解

参考代码

• Python

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

d