🍭 大家好这里是KK爱Coding ，一枚热爱算法的程序员

✨ 本系列打算持续跟新小米近期的春秋招笔试题汇总～

💻 ACM银牌🥈| 多次AK大厂笔试 ｜ 编程一对一辅导

👏 感谢大家的订阅➕ 和 喜欢💗

📧 KK这边最近正在收集近一年互联网各厂的笔试题汇总，如果有需要的小伙伴可以关注后私信一下 KK领取，会在飞书进行同步的跟新。

**

💻听说明天上午要笔美团啦，这里给大家带来一些去年秋招的题目来练练手。

🎉 祝大家明天超常发挥，笔试AK，rp ++++++

**

01.K小姐的植物浇水

问题描述

K小姐有一盆植物，她希望能够在最短的时间内让植物长到至少 $z$ 厘米高。目前植物的高度为 $0$ 厘米。

每天，K小姐可以选择以下两种浇水方式之一：

1. 浇 $x$ 毫升的水，植物高度增加 $x$ 厘米。
2. 浇 $y$ 毫升的水，植物高度增加 $y$ 厘米。需要注意的是，使用第二种浇水方式后，必须至少等待两天才能再次使用该方式。

请你帮助K小姐计算出让植物长到至少 $z$ 厘米高所需的最少天数。

输入格式

输入一行，包含三个整数 $x$、$y$ 和 $z$，分别表示两种浇水方式的水量以及目标植物高度。

输出格式

输出一个整数，表示让植物长到至少 $z$ 厘米高所需的最少天数。

样例输入

1 2 10

样例输出

6

数据范围

• $1\le x,y,z\le 10^9$

题解

本题可以使用二分查找的思想来解决。我们可以二分枚举所需的天数 $d$，判断在 $d$ 天内是否能够让植物长到至少 $z$ 厘米高。

对于每个枚举的天数 $d$，我们可以计算出在这 $d$ 天内使用第二种浇水方式的最大次数为 $\lfloor \frac{d}{3}\rfloor$。然后，我们可以计算出在这 $d$ 天内，使用第一种浇水方式的次数为 $d-\lfloor \frac{d}{3}\rfloor$。

因此，在 $d$ 天内，植物的最大高度为：

$height=x\times (d-\lfloor \frac{d}{3}\rfloor )+y\times \lfloor \frac{d}{3}\rfloor$

如果 $height\ge z$，说明在 $d$ 天内可以让植物长到至少 $z$ 厘米高，我们可以缩小二分的范围；否则，我们需要增大二分的范围。

通过二分查找，我们可以找到最小的满足条件的天数。

时间复杂度：$O(\log z)$，其中 $z$ 为目标植物高度。
空间复杂度：$O(1)$。

参考代码

• Python

def is_feasible(d, x, y, z):num = (d // 3) * y + d * xif d % 3 != 0:num += yreturn num >= zx, y, z = map(int, input().split())
left, right = 0, z // x + 1
while left < right:mid = (left + right) // 2if is_feasible(mid, x, y, z):right = midelse:left = mid + 1
print(right)

• Java

import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner scanner = new Scanner(System.in);int x = scanner.nextInt();int y = scanner.nextInt();int z = scanner.nextInt();int left = 0, right = z / x + 1;while (left < right) {int mid = (left + right) / 2;if (isFeasible(mid, x, y, z)) {right = mid;} else {left = mid + 1;}}System.out.println(right);}public static boolean isFeasible(int d, int x, int y, int z) {long num = (d / 3) * y + d * x;if (d % 3 != 0) {num += y;}return num >= z;}
}

• Cpp

#include <iostream>
using namespace std;int x, y, z;bool isFeasible(int d) {long long int num = (d / 3) * y + d * x;if (d % 3) {num += y;}return num >= z;
}int main() {cin >> x >> y >> z;int left = 0, right = z / x + 1;while (left < right) {int mid = (left + right) / 2;if (isFeasible(mid)) {right = mid;} else {left = mid + 1;}}cout << right;return 0;
}

02.LYA 的公寓租金分摊

问题描述

LYA 是一位年轻有为的创业者,她在城市里拥有 $n$ 栋公寓楼。每栋公寓楼都有若干名租户入住,LYA 自己也在每栋楼里保留了一个住处。现在,是每个月向租户们收取租金的时候了。

对于第 $i$ 栋公寓楼,共有 $k_i$ 名租户(包括 LYA 自己),月租总金额为 $c_i$。为了公平起见,LYA 决定将总租金 $c_i$ 平均分摊给所有租户(包括她自己),每人需支付 $\lceil \frac{c_i}{k_i}\rceil$ 的金额。这里, $\lceil x\rceil$ 表示对实数 $x$ 向上取整。

现在,LYA 希望你能帮她计算每位租户需要支付的租金金额。

输入格式

第一行包含两个正整数 $n$ 和 $m$,分别表示 LYA 拥有的公寓楼数量和城市中租户的总数。$(1<n,m\le 10^5)$

接下来有 $2n$ 行,每两行描述一栋公寓楼的信息:

• 第一行包含两个整数 $k_i$ 和 $c_i$,分别表示该公寓楼的租户总数(包括 LYA)和月租总金额。$(2\le k_i\le m+1,1\le c_i\le 10^9)$
• 第二行包含 $k_i-1$ 个整数,表示每位租户(不包括 LYA)的编号。租户编号在 $1$ 到 $m$ 之间。

输出格式

输出包含 $m$ 个整数,第 $i$ 个整数表示编号为 $i$ 的租户需要支付的租金金额。

样例输入

2 3
3 10
1 2
4 10
1 2 3

样例输出

7 7 3

数据范围

• $1<n,m\le 10^5$
• $2\le k_i\le m+1$
• $1\le c_i\le 10^9$
• 租户编号在 $1$ 到 $m$ 之间

题解

本题要求我们计算每位租户需要支付的租金金额。由于 LYA 自己也算作一名租户,因此每栋公寓楼的实际租户数为输入的 $k_i-1$。

我们可以先创建一个长度为 $m$ 的数组 rent,用于存储每位租户的租金金额,初始值都为 $0$。

然后,对于每栋公寓楼,我们计算出每位租户需要支付的租金金额 $\lceil \frac{c_i}{k_i}\rceil$,然后将其累加到对应租户的租金金额上。

最后,我们将 rent 数组中的租金金额按顺序输出即可。

时间复杂度为 $O(n\times \bar{k})$,其中 $\bar{k}$ 为每栋公寓楼的平均租户数。空间复杂度为 $O(m)$。

参考代码

• Python

n, m = map(int, input().split())
rent = [0] * mfor _ in range(n):k, c = map(int, input().split())cost = (c + k - 1) // kfor x in map(int, input().split()):rent[x - 1] += costprint(*rent)

• Java

import java.io.*;
import java.util.*;public class Main {public static void main(String[] args) throws IOException {BufferedReader br = new BufferedReader(new InputStreamReader(System.in));String[] nm = br.readLine().split(" ");int n = Integer.parseInt(nm[0]);int m = Integer.parseInt(nm[1]);long[] rent = new long[m];for (int i = 0; i < n; ++i) {String[] kc = br.readLine().split(" ");int k = Integer.parseInt(kc[0]);int c = Integer.parseInt(kc[1]);long cost = (c + k - 1) / k;StringTokenizer st = new StringTokenizer(br.readLine());while (st.hasMoreTokens()) {int x = Integer.parseInt(st.nextToken());rent[x - 1] += cost;}}System.out.println(Arrays.stream(rent).mapToObj(Long::toString).collect(Collectors.joining(" ")));}
}

• Cpp

#include <iostream>
using namespace std;int main() {int n, m;cin >> n >> m;long long rent[m] = {0};for (int i = 0; i < n; ++i) {int k, c;cin >> k >> c;long long cost = (c + k - 1) / k;for (int j = 0; j < k - 1; ++j) {int x;cin >> x;rent[x - 1] += cost;}}for (int i = 0; i < m; ++i) {cout << rent[i] << (i == m - 1 ? "\n" : " ");}return 0;
}

03.LYA的魔药配方

问题描述

LYA是一位天才的魔药师，她有一个包含 $n$ 种材料的魔药配方。每种材料都有一个初始的魔力值 $a_i$。

为了制作出更加强大的魔药，LYA可以进行最多 $m$ 次魔力调整操作。每次操作如下：

1. 选择两种不同的材料，设它们的下标为 $i$ 和 $j$（$1\le i<j\le n$）。
2. 选择两个正整数 $x$ 和 $y$，满足 $x\times y=a_i\times a_j$。
3. 将第 $i$ 种材料的魔力值变为 $x$，第 $j$ 种材料的魔力值变为 $y$。

LYA想知道，在最多进行 $m$ 次操作后，魔药配方中所有材料的魔力值之和最大可以达到多少。

输入格式

第一行包含两个整数 $n$ 和 $m$，分别表示魔药材料的数量和最多可以进行的操作次数。

第二行包含 $n$ 个整数 $a_1,a_2,\dots ,a_n$，表示初始时每种材料的魔力值。

输出格式

输出一个整数，表示在最多进行 $m$ 次操作后，魔药配方中所有材料的魔力值之和的最大值。

由于答案可能很大，请输出答案对 $10^9+7$ 取模的结果。

样例输入

6 2
1 2 3 4 5 6

样例输出

128

数据范围

• $1\le m<n\le 10^5$
• $1\le a_i\le 10^5$

题解

本题可以使用贪心算法来解决。

为了使最后的魔力值之和最大，我们需要尽可能地将较大的魔力值调整得更大。具体策略如下：

1. 将材料按照魔力值从小到大排序。
2. 从最大的两个魔力值开始，将它们的乘积赋值给最大的魔力值，并将次大的魔力值设为 $1$。
3. 重复步骤 2，直到进行了 $m$ 次操作或者无法继续操作为止。
4. 计算所有材料的魔力值之和并输出结果。

时间复杂度为 $O(n\log n)$，空间复杂度为 $O(n)$。

参考代码

• Python

n, m = map(int, input().split())
a = list(map(int, input().split()))
mod = 10**9 + 7a.sort()
ptr1, ptr2 = n - 2, n - 1for i in range(m):if ptr1 < 0:breaktemp = (a[ptr1] * a[ptr2]) % moda[ptr1] = 1a[ptr2] = tempptr1 -= 1result = sum(a) % mod
print(result)

• Java

import java.util.Arrays;
import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner scanner = new Scanner(System.in);int[] input = Arrays.stream(scanner.nextLine().split(" ")).mapToInt(Integer::parseInt).toArray();int n = input[0], m = input[1];long[] a = Arrays.stream(scanner.nextLine().split(" ")).mapToLong(Long::parseLong).toArray();long mod = (long) (1e9 + 7);Arrays.sort(a);int ptr1 = n - 2, ptr2 = n - 1;for (int i = 0; i < m && ptr1 >= 0; i++) {long temp = (a[ptr1] * a[ptr2]) % mod;a[ptr1] = 1;a[ptr2] = temp;ptr1--;}long result = 0;for (long num : a) {result = (result + num) % mod;}System.out.println(result);}
}

• Cpp

#include <iostream>
#include <algorithm>
using namespace std;const int mod = 1e9 + 7;int main() {int n, m;cin >> n >> m;long long a[n];for (int i = 0; i < n; i++) {cin >> a[i];}sort(a, a + n);int ptr1 = n - 2, ptr2 = n - 1;for (int i = 0; i < m && ptr1 >= 0; i++) {long long temp = (a[ptr1] * a[ptr2]) % mod;a[ptr1] = 1;a[ptr2] = temp;ptr1--;}long long result = 0;for (int i = 0; i < n; i++) {result = (result + a[i]) % mod;}cout << result << endl;return 0;
}

04.K小姐的礼物盒

问题描述

K小姐有两个礼物盒，每个礼物盒中都装有 $n$ 个礼物。第一个礼物盒中的礼物价值分别为 $a_1,a_2,\dots ,a_n$，第二个礼物盒中的礼物价值分别为 $b_1,b_2,\dots ,b_n$。

K小姐想要重新排列两个礼物盒中的礼物，使得对于每个 $i\in [1,n]$，第一个礼物盒中第 $i$ 个位置的礼物价值 $a_i$ 与第二个礼物盒中第 $i$ 个位置的礼物价值 $b_i$ 之和都满足 $1\le a_i+b_i\le m$。

现在给定 $q$ 组询问，每组询问给定两个礼物盒的初始状态，请判断是否存在一种重排方案满足K小姐的要求。

输入格式

第一行输入一个整数 $q$ $(1\le q\le 30)$，表示询问的组数。

接下来 $q$ 组询问，每组询问格式如下：

第一行两个整数 $n$ $(1\le n\le 500)$ 和 $m$ $(1\le m\le 500)$，分别表示礼物的数量和价值和的上限。

第二行 $n$ 个整数 $a_1,a_2,\dots ,a_n$，表示第一个礼物盒中的礼物价值。

第三行 $n$ 个整数 $b_1,b_2,\dots ,b_n$，表示第二个礼物盒中的礼物价值。

其中，$-500\le a_i,b_i\le 500$。

输出格式

输出 $q$ 行，每行对应一组询问的答案。如果存在满足条件的重排方案，输出 Yes，否则输出 No。

样例输入

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

样例输出

No
Yes

数据范围

• $1\le q\le 30$
• $1\le n\le 500$
• $1\le m\le 500$
• $-500\le a_i,b_i\le 500$

题解

本题可以使用贪心的思想来解决。对于每组询问，我们可以将两个礼物盒中的礼物分别按照价值进行排序，然后考虑将第一个礼物盒中价值最小的礼物与第二个礼物盒中价值最大的礼物配对，依次类推。

对于排序后的两个礼物盒，我们从左右两端开始配对，即第一个礼物盒中的第 $i$ 个礼物与第二个礼物盒中的第 $n-i+1$ 个礼物配对。如果对于每一对配对的礼物，它们的价值和都满足 $1\le a_i+b_{n-i+1}\le m$，那么就存在满足条件的重排方案；否则，不存在满足条件的重排方案。

时间复杂度：对于每组询问，排序的时间复杂度为 $O(n\log n)$，配对检查的时间复杂度为 $O(n)$，总时间复杂度为 $O(q\times (n\log n+n))$。
空间复杂度：$O(n)$，用于存储礼物盒中的礼物价值。

参考代码

• Python

q = int(input())for _ in range(q):n, m = map(int, input().split())a = list(map(int, input().split()))b = list(map(int, input().split()))a.sort()b.sort(reverse=True)flag = Truefor i in range(n):if not (1 <= a[i] + b[i] <= m):flag = Falsebreakprint("Yes" if flag else "No")

• Java

import java.util.Arrays;
import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner sc = new Scanner(System.in);int q = sc.nextInt();while (q-- > 0) {int n = sc.nextInt();int m = sc.nextInt();int[] a = new int[n];int[] b = new int[n];for (int i = 0; i < n; i++) {a[i] = sc.nextInt();}for (int i = 0; i < n; i++) {b[i] = sc.nextInt();}Arrays.sort(a);Arrays.sort(b);reverse(b);boolean flag = true;for (int i = 0; i < n; i++) {if (a[i] + b[i] < 1 || a[i] + b[i] > m) {flag = false;break;}}System.out.println(flag ? "Yes" : "No");}}private static void reverse(int[] arr) {int left = 0, right = arr.length - 1;while (left < right) {int temp = arr[left];arr[left] = arr[right];arr[right] = temp;left++;right--;}}
}

• Cpp

#include <iostream>
#include <algorithm>
using namespace std;const int MAX_N = 500;int main() {int q;cin >> q;while (q--) {int n, m;cin >> n >> m;int a[MAX_N], b[MAX_N];for (int i = 0; i < n; i++) {cin >> a[i];}for (int i = 0; i < n; i++) {cin >> b[i];}sort(a, a + n);sort(b, b + n, greater<int>());bool flag = true;for (int i = 0; i < n; i++) {if (a[i] + b[i] < 1 || a[i] + b[i] > m) {flag = false;break;}}cout << (flag ? "Yes" : "No") << endl;}return 0;
}

05.LYA 的平均分目标

问题描述

LYA 是一名刚入学的大学新生,她的专业课程有 $n$ 门。在大一第一学期结束时,她的任课老师给每门课程都打了分数。这 $n$ 个分数构成了一个数组 $a_1,a_2,\dots ,a_n$。

作为一名学霸,LYA 希望自己的平均分能达到 $k$ 分。为此,她想从这 $n$ 门课程中选出一些连续的课程,使得这些课程的平均分恰好等于 $k$。现在,她想知道最多可以选出多少门课程。

输入格式

第一行包含两个正整数 $n$ 和 $k$,分别表示课程总数和目标平均分。

第二行包含 $n$ 个正整数 $a_1,a_2,\dots ,a_n$,表示每门课程的分数。

输出格式

输出一个整数,表示 LYA 最多可以选出的满足条件的连续课程数量。

样例输入

5 2
1 3 2 4 1

样例输出

3

数据范围

• $1\le n\le 10^5$
• $1\le k,a_i\le 10^9$

题解

本题可以使用前缀和 + 哈希表的方法来解决。

首先,我们可以计算出数组 $a$ 的前缀和数组 $sum$,其中 $sum[i]$ 表示前 $i$ 个元素的和。为了方便计算,我们可以在数组 $sum$ 的开头添加一个元素 $0$,即 $sum[0]=0$。

接下来,我们遍历前缀和数组 $sum$,对于每个位置 $i$,我们计算 $sum[i]-i\times k$。如果当前值出现过,说明存在一个子数组,其元素和为 $i\times k$,平均值为 $k$。我们可以用哈希表来记录每个值第一次出现的位置,从而快速判断当前值是否出现过。

最后,我们取出最长的满足条件的子数组长度即可。

时间复杂度为 $O(n)$,空间复杂度为 $O(n)$。

参考代码

• Python

n, k = map(int, input().split())
a = list(map(int, input().split()))s = [0] * (n + 1)
for i in range(1, n + 1):s[i] = s[i - 1] + a[i - 1] - kpos = {0: 0}
ans = 0
for i in range(1, n + 1):if s[i] in pos:ans = max(ans, i - pos[s[i]])else:pos[s[i]] = iprint(ans)

• Java

import java.io.*;
import java.util.*;public class Main {public static void main(String[] args) throws IOException {BufferedReader br = new BufferedReader(new InputStreamReader(System.in));String[] line = br.readLine().split(" ");int n = Integer.parseInt(line[0]);long k = Long.parseLong(line[1]);long[] a = new long[n];line = br.readLine().split(" ");for (int i = 0; i < n; i++) {a[i] = Long.parseLong(line[i]);}long[] s = new long[n + 1];for (int i = 1; i <= n; i++) {s[i] = s[i - 1] + a[i - 1] - k;}Map<Long, Integer> pos = new HashMap<>();pos.put(0L, 0);int ans = 0;for (int i = 1; i <= n; i++) {if (pos.containsKey(s[i])) {ans = Math.max(ans, i - pos.get(s[i]));} else {pos.put(s[i], i);}}System.out.println(ans);}
}

• Cpp

#include <iostream>
#include <vector>
#include <unordered_map>using namespace std;int main() {int n;long long k;cin >> n >> k;vector<long long> a(n);for (int i = 0; i < n; i++) {cin >> a[i];}vector<long long> s(n + 1);for (int i = 1; i <= n; i++) {s[i] = s[i - 1] + a[i - 1] - k;}unordered_map<long long, int> pos;pos[0] = 0;int ans = 0;for (int i = 1; i <= n; i++) {if (pos.count(s[i])) {ans = max(ans, i - pos[s[i]]);} else {pos[s[i]] = i;}}cout << ans << endl;return 0;
}

写在最后

📧 KK这边最近正在收集近一年互联网各厂的笔试题汇总，如果有需要的小伙伴可以关注后私信一下 KK领取，会在飞书进行同步的跟新。