🍭 大家好这里是KK爱Coding ，一枚热爱算法的程序员
✨ 本系列打算持续跟新淘天近期的春秋招笔试题汇总～
💻 ACM银牌🥈| 多次AK大厂笔试 ｜ 编程一对一辅导
👏 感谢大家的订阅➕ 和 喜欢💗
📧 KK这边最近正在收集近一年互联网各厂的笔试题汇总，如果有需要的小伙伴可以关注后私信一下 KK领取，会在飞书进行同步的跟新。
文章目录
-
- 01.数组的最大权值
-
- 题目描述
- 输入格式
- 输出格式
- 样例输入
- 样例输出
- 数据范围
- 题解
- 参考代码
- 02.卢小姐的城市之旅
-
- 题目描述
- 输入格式
- 输出格式
- 样例输入
- 样例输出
- 样例解释
- 数据范围
- 题解
- 参考代码
- 03.卢小姐的元素调整之旅
-
- 问题描述
- 输入格式
- 输出格式
- 样例输入
- 样例输出
- 数据范围
- 题解
- 参考代码
- 写在最后
- 📧 KK这边最近正在收集近一年互联网各厂的笔试题汇总，如果有需要的小伙伴可以关注后私信一下 KK领取，会在飞书进行同步的跟新。
01.数组的最大权值
题目描述
K小姐有一个长度为 的数组
，她定义一个数组的权值为数组中不同数字的个数。
现在，K小姐想从数组 中选出
个数字，使得这
个数字组成的新数组的权值最大。你能帮助K小姐找出最大的权值吗？
输入格式
第一行包含两个正整数 和
（
），表示数组
的长度和需要选择的数字个数。
第二行包含 个正整数
（
），表示数组
的元素。
输出格式
输出一个正整数，表示选出 个数字组成新数组的最大权值。
样例输入
4 3
1 1 2 2
样例输出
2
数据范围
题解
这个问题可以用贪心的思想来解决。为了使选出的 个数字组成的新数组的权值最大，我们需要尽可能选择不同的数字。
我们可以先把原数组 中的所有数字放入一个集合中，这样就可以去掉重复的数字。然后，我们比较集合的大小和
的大小：
- 如果集合的大小大于等于
，那么我们可以直接从集合中选出
- 如果集合的大小小于
所以，最大权值就是 和集合大小的较小值。
时间复杂度：，需要遍历一次数组来建立集合。
空间复杂度：，需要一个集合来存储不同的数字。
参考代码
- Python
import sys
def main():
n, k = map(int, sys.stdin.readline().split())
nums = set(map(int, sys.stdin.readline().split()))
print(min(len(nums), k))
if __name__ == "__main__":
main()
- 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[] nk = br.readLine().split(" ");
int n = Integer.parseInt(nk[0]);
int k = Integer.parseInt(nk[1]);
String[] numsStr = br.readLine().split(" ");
Set<Integer> nums = new HashSet<>();
for (String num : numsStr) {
nums.add(Integer.parseInt(num));
}
System.out.println(Math.min(nums.size(), k));
}
}
- Cpp
#include <iostream>
#include <unordered_set>
using namespace std;
int main() {
int n, k;
cin >> n >> k;
unordered_set<int> nums;
for (int i = 0; i < n; i++) {
int num;
cin >> num;
nums.insert(num);
}
cout << min((int)nums.size(), k) << endl;
return 0;
}
02.卢小姐的城市之旅
题目描述
卢小姐计划去旅行，她要走遍 个城市。从一个城市到相邻的城市需要消耗
单位的体力。每个城市都有特色美食，每份售价为
，卢小姐可以在每个城市购买任意份美食。
卢小姐想要用最少的花费走完全程，但是她希望每个城市的美食不要吃太多，即在一个城市重复进餐的次数的最大值最小。
卢小姐想知道一种满足上述条件的美食购买方案。如果有多种方案，输出任意一种即可。
输入格式
第一行输入一个整数 （
），表示城市个数。
第二行输入 个整数，表示每个城市的美食售价
（
）。
输出格式
输出一行整数，表示每个城市购买的美食份数。
样例输入
4
1 2 1 4
样例输出
2 0 1 0
样例解释
在第 个城市购买
份美食，花费
。
在第 个城市购买
份美食，花费
。
在第 个城市购买
份美食，花费
。
在第 个城市购买
份美食，花费
。
此时总花费为 ，在同一个城市重复进餐次数的最大值为
（第
个城市）。
数据范围
题解
本题可以使用贪心 + 优先队列来解决，即所谓反悔贪心
我们可以维护一个优先队列，存储每个城市的美食售价和当前在该城市进餐的次数。每次从优先队列中取出售价最低且进餐次数最少的城市，在该城市多购买一份美食，然后将其重新插入优先队列。重复这个过程直到到达最后一个城市。
这样做的正确性在于，我们总是选择售价最低且进餐次数最少的城市购买美食，可以尽量均匀地分配进餐次数，从而使得在同一个城市重复进餐次数的最大值最小。
时间复杂度为 ，空间复杂度为
。
参考代码
- Python
import heapq
n = int(input())
a = list(map(int, input().split()))
pq = [(a[i], 0, i) for i in range(n)]
heapq.heapify(pq)
ans = [0] * n
for _ in range(n - 1):
price, cnt, idx = heapq.heappop(pq)
ans[idx] += 1
heapq.heappush(pq, (price, cnt + 1, idx))
print(*ans)
- Java
import java.util.*;
class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int[] a = new int[n];
for (int i = 0; i < n; i++) {
a[i] = sc.nextInt();
}
PriorityQueue<int[]> pq = new PriorityQueue<>((x, y) ->
x[0] != y[0] ? x[0] - y[0] : x[1] - y[1]);
for (int i = 0; i < n; i++) {
pq.offer(new int[]{a[i], 0, i});
}
int[] ans = new int[n];
for (int i = 0; i < n - 1; i++) {
int[] top = pq.poll();
ans[top[2]]++;
pq.offer(new int[]{top[0], top[1] + 1, top[2]});
}
for (int x : ans) {
System.out.print(x + " ");
}
}
}
- Cpp
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
typedef pair<int, pair<int, int>> PII;
int main() {
int n;
cin >> n;
vector<int> a(n);
for (int i = 0; i < n; i++) {
cin >> a[i];
}
priority_queue<PII, vector<PII>, greater<PII>> pq;
for (int i = 0; i < n; i++) {
pq.emplace(a[i], make_pair(0, i));
}
vector<int> ans(n);
for (int i = 0; i < n - 1; i++) {
auto top = pq.top();
pq.pop();
int price = top.first, cnt = top.second.first, idx = top.second.second;
ans[idx]++;
pq.emplace(price, make_pair(cnt + 1, idx));
}
for (int x : ans) {
cout << x << " ";
}
return 0;
}
03.卢小姐的元素调整之旅
问题描述
K小姐和A先生在玩一款名为“元素调整”的游戏。K小姐有一串宝石，每颗宝石都有一个能量值。为了保持宝石的和谐，K小姐希望通过调整能量值，使得她的宝石串中的能量值不递减，并且每颗宝石的能量值必须与A先生提供的宝石能量值匹配。
K小姐可以通过施加魔法来增加或减少宝石的能量值（每次操作改变 单位能量）。她想知道，为了达到目标，最少需要施展多少次魔法。
输入格式
第一行包含两个正整数 ，分别表示 K小姐和 A先生宝石串的长度。
第二行共 个空格分开的正整数
，表示 K小姐宝石串的初始能量值。
第三行共 个空格分开的正整数
，表示 A先生宝石串的能量值。
输出格式
输出一个整数，表示 K小姐达到目标所需的最少魔法施展次数。
样例输入
5 4
3 5 3 8 10
1 2 3 4
样例输出
12
数据范围
题解
要使 K小姐的宝石串能量值不递减且每颗宝石的能量值都存在于 A先生的宝石串中，我们可以采用动态规划的方法。我们定义状态 为考虑到 K小姐的前
颗宝石，并且第
颗宝石的能量调整为 A先生宝石串中第
颗的能量值时，所需的最小魔法施展次数。状态转移方程为：
最终答案为 。
参考代码
- Python
INF = float('inf')
n, m = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
b.sort()
dp = [[INF] * (m + 1) for _ in range(n + 1)]
for j in range(m + 1):
dp[0][j] = 0
for i in range(1, n + 1):
temp = dp[i - 1][0];
for j in range(1, m + 1):
temp = min(temp, dp[i - 1][j])
val = abs(a[i - 1] - b[j - 1])
dp[i][j] = min(dp[i - 1][j], temp) + val
ans = min(dp[n])
print(ans)
- 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 INF = Integer.MAX_VALUE;
int n = sc.nextInt(), m = sc.nextInt();
int[] a = new int[n];
int[] b = new int[m];
for (int i = 0; i < n; i++) {
a[i] = sc.nextInt();
}
for (int i = 0; i < m; i++) {
b[i] = sc.nextInt();
}
Arrays.sort(b);
int[][] dp = new int[n + 1][m + 1];
for (int[] row : dp) {
Arrays.fill(row, INF);
}
for (int j = 0; j <= m; j++) {
dp[0][j] = 0;
}
for (int i = 1; i <= n; i++) {
int temp = dp[i - 1][0];
for (int j = 1; j <= m; j++) {
temp - Math.min(temp, dp[i - 1][j]);
int val = Math.abs(a[i - 1] - b[j - 1]);
dp[i][j] = Math.min(dp[i - 1][j], temp) + val;
}
}
int ans = Arrays.stream(dp[n]).min().orElse(INF);
System.out.println(ans);
}
}
- Cpp
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int main() {
const int INF = 1e9;
int n, m;
cin >> n >> m;
vector<int> a(n), b(m);
for (int i = 0; i < n; i++) {
cin >> a[i];
}
for (int i = 0; i < m; i++) {
cin >> b[i];
}
sort(b.begin(), b.end());
vector<vector<int>> dp(n + 1, vector<int>(m + 1, INF));
for (int j = 0; j <= m; j++) {
dp[0][j] = 0;
}
for (int i = 1; i <= n; i++) {
int temp = dp[i - 1][0];
for (int j = 1; j <= m; j++) {
temp = min(temp, dp[i - 1][j]);
int val = abs(a[i - 1] - b[j - 1]);
dp[i][j] = min(dp[i - 1][j], temp) + val;
}
}
int ans = *min_element(dp[n].begin(), dp[n].end());
cout << ans << endl;
return 0;
}
写在最后
📧 KK这边最近正在收集近一年互联网各厂的笔试题汇总，如果有需要的小伙伴可以关注后私信一下 KK领取，会在飞书进行同步的跟新。
版权声明：本文为博主作者：KK爱Coding原创文章，版权归属原作者，如果侵权，请联系我们删除！
原文链接：https://blog.csdn.net/Qmtdearu/article/details/137359167
