【秋招突围】2024届秋招-阿里系列笔试题-第二套
🍭 大家好这里是清隆学长 ,一枚热爱算法的程序员
✨ 本系计划跟新各公司春秋招的笔试题
👏 感谢大家的订阅➕ 和 喜欢💗
📖 写在前面
夏天来了 秋招还会远吗?
前不久春招也算是圆满结束咯,大家有拿到心仪的 offer吗? 接下来互联网的秋招也快来啦,小伙伴们有开始准备了吗? 本次给大家带来24届秋招 阿里系 的笔试题目三语言解析(Java/Python/Cpp)
✨ 01.K小姐的魔药配方
问题描述
K小姐是一位魔药大师,她有 种魔药材料。每种材料都包含一定比例的稀有元素和普通元素。第
种材料中,稀有元素的比例为
,普通元素的比例为
。
K小姐想要配制一种魔药,要求稀有元素的比例不低于 。她可以选择任意多种材料,将它们混合在一起。
请问,K小姐最多可以配制出多少份这样的魔药?
输入格式
第一行包含一个正整数 (
),表示材料的种类数。
第二行包含 个整数
(
),表示每种材料中稀有元素的比例。
第三行包含 个整数
(
),表示每种材料中普通元素的比例。
保证对于每种材料,有 。
输出格式
输出一个整数,表示K小姐最多可以配制出的魔药份数。
样例输入
3
50 60 30
50 40 70
样例输出
110
数据范围
题解
我们可以先将材料按照稀有元素的比例从高到低排序。然后从前往后选择材料,直到选择的材料中稀有元素的总比例不再大于等于 。
设前 种材料中,稀有元素的总比例为
,普通元素的总比例为
。如果
,那么前
种材料就可以用来配制魔药。
我们可以用贪心的思想来证明这一做法的正确性。对于当前选择的材料,如果替换成任何一种未选择的材料,那么稀有元素的总比例一定会下降,因为未选择的材料的稀有元素比例一定小于等于当前材料。因此,我们的选择方案是最优的。
时间复杂度为 ,空间复杂度为
。
参考代码
- Python
n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
materials = sorted(zip(a, b), reverse=True)
sum_a = sum_b = 0
ans = 0
for x, y in materials:
if sum_a + x >= sum_b + y:
sum_a += x
sum_b += y
ans += x
else:
break
print(ans)
- Java
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = 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();
}
int[][] materials = new int[n][2];
for (int i = 0; i < n; i++) {
materials[i] = new int[]{a[i], b[i]};
}
Arrays.sort(materials, (x, y) -> y[0] - x[0]);
int sumA = 0, sumB = 0;
int ans = 0;
for (int[] m : materials) {
if (sumA + m[0] >= sumB + m[1]) {
sumA += m[0];
sumB += m[1];
ans += m[0];
} else {
break;
}
}
System.out.println(ans);
}
}
- Cpp
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1e5 + 10;
int a[N], b[N];
int main() {
int n;
cin >> n;
for (int i = 0; i < n; i++) {
cin >> a[i];
}
for (int i = 0; i < n; i++) {
cin >> b[i];
}
vector<pair<int, int>> materials;
for (int i = 0; i < n; i++) {
materials.emplace_back(a[i], b[i]);
}
sort(materials.begin(), materials.end(), greater<pair<int, int>>());
int sumA = 0, sumB = 0;
int ans = 0;
for (auto& m : materials) {
if (sumA + m.first >= sumB + m.second) {
sumA += m.first;
sumB += m.second;
ans += m.first;
} else {
break;
}
}
cout << ans << endl;
return 0;
}
⚡️ 02.K小姐的魔法阵
问题描述
K小姐在探索一座神秘的魔法塔时,发现了一个奇特的魔法阵。这个魔法阵由 个魔法石组成,每个魔法石上都刻有一个正整数。然而,由于年代久远,魔法阵上的数字已经变得模糊不清。
K小姐凭借自己的魔法知识,了解到这个魔法阵的数字排列满足以下规律:如果将魔法石上的数字按顺序排列成一个序列 ,那么对于任意的
,都有
。
现在,K小姐希望你能帮助她还原这个神秘的魔法阵。
输入格式
输入只包含一个正整数 (
),表示魔法阵中魔法石的数量。
输出格式
如果能够还原出符合条件的魔法阵,则输出一行,包含 个正整数,表示还原后的魔法阵中每个魔法石上的数字。如果有多个可能的解,输出任意一个即可。
如果无法还原出符合条件的魔法阵,则输出一行,包含一个整数 。
样例输入
5
样例输出
2 5 3 1 4
数据范围
题解
我们可以根据给定的规律,直接构造出符合条件的魔法阵。
首先,我们可以发现,如果 为
的倍数或者
的倍数加
,那么就一定存在符合条件的魔法阵。否则,无法构造出符合条件的魔法阵。
对于 为
的倍数或者
的倍数加
的情况,我们可以按照以下方式构造魔法阵:
- 对于
为奇数且
,令
,
。
- 对于
为奇数且
,令
,
。
- 如果
为奇数,令
。
按照上述方式构造出的序列 即为符合条件的魔法阵。
时间复杂度为 ,空间复杂度为
。
参考代码
- Python
n = int(input())
a = [0] * (n + 1)
if n % 4 == 0 or n % 4 == 1:
for i in range(1, n // 2 + 1, 2):
a[i] = i + 1
a[i + 1] = n - i + 1
a[n - i + 1] = n - i
a[n - i] = i
if n % 2 != 0:
a[n // 2 + 1] = n // 2 + 1
print(' '.join(map(str, a[1:])))
else
剩余60%内容,订阅专栏后可继续查看/也可单篇购买
这里收集了超全的互联网春秋招笔试题,欢迎大家的订阅,会持续跟新的