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

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

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

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

✨ 笔试合集传送们 -> 🧷春秋招笔试合集

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

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

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

🌈 小米秋招笔试，来啦！！！

🍥 本次是DP+贪心场，第二题很容易误导往DP方面想，当然也能做只不过需要优化

1️⃣ 01背包的变种，即求01背包是否能恰好装满

2️⃣ 贪心，分别枚举递增和递减的情况，有任意一种满足即可

本次的二题已全上OJ，支持在线评测啦~

🧸 01.K小姐的玩具 评测链接🔗

问题描述

在一个阳光明媚的下午，K小姐决定整理她的玩具。她有一个容量为 $N$ 的箱子，以及 $n$ 个不同大小的玩具，每个玩具的大小分别为 $a[i]$。除了这些玩具，K小姐还有 $c$ 个大小均为 $1$ 的填充物，这些填充物是她参加各种活动时的纪念品。

K小姐希望能够将这些玩具和填充物放入箱子中，恰好装满箱子，不留任何空隙。她想知道是否可以通过选择一些玩具（包括填充物）来实现这个目标。

当然，如果填充物足够多，她也可以选择用填充物完全填满整个箱子，这样也会让她感到很开心！

输入格式

第一行包含一个整数 $T$，表示数据组数。

对于每组数据:

第一行包含三个整数 $N$、$n$ 和 $c$，分别表示箱子的容量、玩具的数量以及填充物的数量。

第二行包含 $n$ 个整数 $a,a,\dots ,a[n]$，分别表示这 $n$ 个玩具的大小。

$1\le T\le 100,1\le n\le 500,1\le N,c,a[i]\le 1000$

输出格式

输出 $T$ 行，分别表示每组数据的答案。

对于每组数据，如果可以恰好装满箱子，输出 “YES”；否则输出 “NO”。

样例输入

2
10 4 1
2 3 5 7
10 1 3
6

样例输出

YES
NO

数据范围

• 每组数据中，箱子的容量、玩具数量和填充物数量均在上述范围内。

题解

动态规划

这个问题实际上是一个经典的背包问题。我们需要确定是否可以选择一些玩具和填充物，使得它们的总大小恰好等于箱子的容量 $N$：

动态规划：定义一个数组 dp，其中 dp[j] 表示是否可以用选定的玩具组合成大小为 $j$ 的总和。初始时，dp[0] 为 true（表示不选任何玩具时总和为0）。

状态转移：对于每个玩具，从后向前更新 dp 数组，对于当前的玩具 a[i]，如果之前可以组合出大小为 j - a[i] 的总和，那么就可以组合出大小为 j 的总和。

检查结果：在更新完所有玩具后，我们检查从大到小的 dp 数组，如果存在某个 i 满足 dp[i] 为 true 且 N - i <= c（即剩余空间可以用填充物填满），则返回 “YES”；否则返回 “NO”。

参考代码

🔒订阅专栏后解锁 $\to$ 🧷春秋招笔试合集

♾️ 02.K小姐的排序挑战 评测链接🔗

问题描述

K小姐是一位热爱数学的女孩。一天，她在公园里遇到了她的朋友们，他们正在讨论如何将两个数组进行排序。K小姐决定帮助他们。她得到了两个长度为 $n$ 的数组 $a[]$ 和 $b[]$，并且可以在这两个数组对应的位置进行交换操作，即选择一个位置 $i$，交换 $a[i]$ 和 $b[i]$。K小姐可以进行任意次数的交换（包括 $0$ 次），她想知道是否可以通过这些操作使得至少一个数组变得有序。

在这里，"有序"指的是数组单调不减（升序）或者单调不增（降序）。现在，K小姐希望你能帮她判断，是否能够通过这些交换操作使得至少一个数组变得有序。

输入格式

第一行包含一个整数 $T$，表示数据组数。
对于每组数据：

• 第一行包含一个整数 $n$，表示数组的长度。
• 第二行包含 $n$ 个整数 $a_1,a_2,\dots ,a_n$，表示数组 $a$。
• 第三行包含 $n$ 个整数 $b_1,b_2,\dots ,b_n$，表示数组 $b$。

输出格式

输出 $T$ 行，每行表示对应数据组的答案。如果能够通过交换操作使至少一个数组变得有序，输出 “YES”；否则输出 “NO”。

样例输入

2
5
1 3 5 2 4
5 2 3 4 1
7
1 2 3 4 3 2 1
4 3 2 1 2 3 4

样例输出

YES
NO

数据范围

• $1\le T\le 100$
• $1\le n\le 10000$
• $1\le a_i,b_i\le 10000$

题解

贪心

我们需要考虑两种可能的排序方式：升序和降序。对于每个位置，都有两个选择：保留原数组的元素或者与另一个数组交换。

解题思路如下：

1. 每个位置的两个元素排序，较小的放在前面。这样可以简化后续的处理。

2. 尝试构造一个升序序列：

   • 从第一个元素开始，记录当前的最小值。
   • 对于每个位置，如果较小的元素大于等于当前最小值，我们选择它；否则，我们尝试选择较大的元素。
   • 如果两个元素都小于当前最小值，说明无法构造升序序列。

3. 同样的方法，尝试构造一个降序序列：

   • 从第一个元素开始，记录当前的最大值。
   • 对于每个位置，如果较大的元素小于等于当前最大值，我们选择它；否则，我们尝试选择较小的元素。
   • 如果两个元素都大于当前最大值，说明无法构造降序序列。

4. 如果能够构造出升序或降序序列中的任意一个，答案就是 “YES”，否则就是 “NO”。

时间复杂度分析：只需要遍历一次数组，对每个位置进行常数时间的操作，所以时间复杂度是 $O(n)$。考虑到有 $T$ 组测试数据，总的时间复杂度是 $O(T\cdot n)$。在给定的数据范围内（$T\le 100$，$n\le 10000$），这个复杂度是可以接受的。

参考代码

🔒订阅专栏后解锁 $\to$ 🧷春秋招笔试合集