【秋招笔试】8.25蚂蚁秋招(算法岗)-三语言题解

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

💻 ACM金牌团队🏅️ | 多次AK大厂笔试｜编程一对一辅导

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

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

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

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

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

🧩 备战秋招还没订阅的朋友们可以冲一下啦，当试题收集至 100 套后，价格会进行一波调整~

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

alt

🪔蚂蚁笔试题来啦！！！！

🍥 本次难度中等，最后一题需要转换，算法岗共有3题，其中第二题是一道专业相关对的题，这边就不放上来了

1️⃣ 贪心+枚举

2️⃣ 有点难度，需要转换成最小生成树来做

🪕 01.LYA的音乐推荐系统

问题描述

LYA是一位热爱音乐的大学生，她正在开发一个音乐推荐系统。系统中有两个数组，一个代表用户的音乐偏好评分，另一个代表歌曲的特征评分。LYA想要找出最佳的用户-歌曲匹配度，以此来推荐最适合的音乐。

匹配度的计算方式是用户偏好评分与歌曲特征评分的乘积。LYA希望找出所有可能组合中的最大匹配度，作为系统的推荐依据。

输入格式

第一行输入一个整数 $n\ (1 \leq n \leq 2 \times 10^5)$ ，表示用户偏好评分和歌曲特征评分的数量。

第二行输入 $n$ 个整数 $a_1, a_2, \ldots, a_n\ (-10^6 \leq a_i \leq 10^6)$ ，表示用户的音乐偏好评分。

第三行输入 $n$ 个整数 $b_1, b_2, \ldots, b_n\ (-10^6 \leq b_i \leq 10^6)$ ，表示歌曲的特征评分。

输出格式

输出一个整数，表示最大的匹配度。

样例输入

5
1 2 3 4 5
5 4 3 2 1

样例输出

数据范围

$1 \leq n \leq 2 \times 10^5$
$-10^6 \leq a_i, b_i \leq 10^6$

题解

关键思路是：最大的乘积一定来自于两个数组中绝对值最大的元素的乘积。：

如果两个最大的数都是正数，它们的乘积显然是最大的。
如果两个最小的数都是负数，它们的乘积也是正数，可能是最大的。
如果一个数组的最大值是正数，另一个是负数，那么它们的乘积可能是负数，不会是最大值。

因此，只需要找出每个数组中的最大值和最小值，然后比较它们的乘积即可。

参考代码

Python

# 读取输入
n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))

# 找出a数组的最大值和最小值
max_a = max(a)
min_a = min(a)

# 找出b数组的最大值和最小值
max_b = max(b)
min_b = min(b)

# 计算四种可能的乘积，并找出最大值
result = max(max_a * max_b, min_a * min_b, max_a * min_b, min_a * max_b)

# 输出结果
print(result)

Java

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        
        // 读取输入
        int n = scanner.nextInt();
        int[] a = new int[n];
        int[] b = new int[n];
        
        // 读取a数组
        for (int i = 0; i < n; i++) {
            a[i] = scanner.nextInt();
        }
        
        // 读取b数组
        for (int i = 0; i < n; i++) {
            b[i] = scanner.nextInt();
        }
        
        // 找出a数组的最大值和最小值
        int maxA = a[0], minA = a[0];
        for (int i = 1; i < n; i++) {
            maxA = Math.max(maxA, a[i]);
            minA = Math.min(minA, a[i]);
        }
        
        // 找出b数组的最大值和最小值
        int maxB = b[0], minB = b[0];
        for (int i = 1; i < n; i++) {
            maxB = Math.max(maxB, b[i]);
            minB = Math.min(minB, b[i]);
        }
        
        // 计算四种可能的乘积，并找出最大值
        long result = Math.max(Math.max((long)maxA * maxB, (long)minA * minB),
                               Math.max((long)maxA * minB, (long)minA * maxB));
        
        // 输出结果
        System.out.println(result);
    }
}

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    int n;
    cin >> n;
    
    // 读取a数组
    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    
    // 读取b数组
    vector<int> b(n);
    for (int i = 0; i < n; i++) {
        cin >> b[i];
    }
    
    // 找出a数组的最大值和最小值
    auto [minA, maxA] = minmax_element(a.begin(), a.end());
    
    // 找出b数组的最大值和最小值
    auto [minB, maxB] = minmax_element(b.begin(), b.end());
    
    // 计算四种可能的乘积，并找出最大值
    long long result = max({
        (long long)*maxA * *maxB,
        (long long)*minA * *minB,
        (long long)*maxA * *minB,
        (long long)*minA * *maxB
    });
    
    // 输出结果
    cout << result << endl;
    
    return 0;
}