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

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

✨ 笔试合集传送们 -> 🧷学长刷题笔记

🍒 本专栏已收集 140+ 套题 🍄 题面描述等均已改编，如果和你实际看到的题面描述不一样请理解，做法和题目本质基本不变。

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

🍥 本次的京东是较为简单的一场，前两题比较白给，最后一题是最小生成树，看出来也就不难了

1️⃣ 前后缀分解求最大乘积，比较简单

2️⃣ 自定义排序

3️⃣ 最小生成树的应用，不难

🎗️ 01.LYA 的珍珠项链

评测链接🔗

问题描述

LYA 是一位珠宝设计师，她最近设计了一条独特的珍珠项链。这条项链由 颗珍珠组成，每颗珍珠都有其独特的价值。LYA 想要将这条项链切割成两部分，以制作成一对手链。

为了使这对手链看起来协调，LYA 决定将项链切割成两部分，使得左边部分珍珠的总价值乘以右边部分珍珠的总价值最小。她希望你能帮她计算出这个最小值。

输入格式

第一行输入一个整数 ，表示珍珠项链的长度。

第二行输入 个整数 ，表示每颗珍珠的价值。

输出格式

输出一个整数，表示切割后两部分珍珠总价值的乘积的最小值。

样例输入

5
1 2 3 4 5

样例输出

14

样例解释

将项链在第一颗珍珠后切割，左边部分价值为 1，右边部分价值为 14（2+3+4+5=14），乘积为 14，这是最小的可能值。

数据范围

• 
• 

题解

前后缀分解

1. 算出总和 后对原数组进行遍历
2. 维护一个 表示数组左边的和，最后答案为 min()

⚠️ 会爆 int，CPP和Java选手要注意

参考代码

• Python

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

# 计算总和
total = sum(a)

# 初始化变量
left_sum = 0
min_product = float('inf')

# 遍历计算最小乘积
for i in range(n - 1):
    left_sum += a[i]
    right_sum = total - left_sum
    min_product = min(min_product, left_sum * right_sum)

# 输出结果
print(min_product)

• Java

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        
        // 读取输入
        int n = scanner.nextInt();
        long[] a = new long[n];
        long total = 0;
        
        for (int i = 0; i < n; i++) {
            a[i] = scanner.nextLong();
            total += a[i];
        }
        
        // 计算最小乘积
        long leftSum = 0;
        long minProduct = Long.MAX_VALUE;
        
        for (int i = 0; i < n - 1; i++) {
            leftSum += a[i];
            long rightSum = total - leftSum;
            minProduct = Math.min(minProduct, leftSum * rightSum);
        }
        
        // 输出结果
        System.out.println(minProduct);
    }
}

• Cpp

#include <iostream>
#include <vector>
#include <climits>

using namespace std;

typedef long long LL;

int main() {
    int n;
    cin >> n;
    
    vector<LL> a(n);
    LL total = 0;
    
    // 读取输入并计算总和
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        total += a[i];
    }
    
    LL left_sum = 0;
    LL min_product = LLONG_MAX;
    
    // 遍历计算最小乘积
    for (int i = 0; i < n - 1; i++) {
        left_sum += a[i];
        LL right_sum = total - left_sum;
        min_product = min(min_product, left_sum * right_sum);
    }
    
    // 输出结果
    cout << min_product << endl;
    
    return 0;
}

02.LYA的书籍整理

评测链接🔗

问题描述

LYA是一位图书馆管理员，她最近收到了一批新的书籍。这些书籍需要按照特定的规则进行排序和整理。LYA发现每本书的书名都是由小写字母组成的，但图书馆有一套独特的字母排序规则。

为了帮助LYA更好地整理这些书籍，你需要编写一个程序，根据给定的字母排序规则，对书名进行排序。排序规则如下：

1. 比较两个书名时，从左到右逐个字符比较。
2. 字符的大小关系由给定的字母顺序决定。
3. 如果一个书名是另一个书名的前缀，较短的书名排在前面。

输入格式

第一行输入一个字符串，包含 26 个不同的小写字母，表示字母的排序规则。字母在字符串中出现的顺序即为它们的排序顺序。

第二行输入一个整数 ，表示书籍的数量。

接下来 行，每行包含一个小写字母组成的字符串 ，表示一本书的书名。

输出格式

按照排序规则从小到大输出排序后的书名，每行一个字符串。

样例输入

abcdefgijklmnpqrstuvwxyz
3
aaaa
aac
aaaa

样例输出

aaa
aac
aaaa

数据范围

• 
• 

题解

自定义排序

按照给定的字符权重进行自定义排序。

还有一种简单的办法是直接吧字符串映射成一个 [0, 25] 的权值数组，直接按照默认排序

参考代码

• Python

# 读取字母顺序和书籍数量
alpha_order = input().strip()
n = int(input())

# 创建字母到索引的映射
char_rank = {c: i for i, c in enumerate(alpha_order)}

# 自定义比较函数
def compare(s1, s2):
    for c1, c2 in zip(s1, s2):
        if c1 != c2:
            return char_rank[c1] - char_rank[c2]
    return len(s1) - len(s2)

# 读取并排序书名
books = [input().strip() for _ in range(n)]
books.sort(key=functools.cmp_to_key(compare))

# 输出排序结果
for book in books:
    print(book)

• Java

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        
        // 读取字母顺序
        String alphaOrder = sc.nextLine();
        
        // 创建字母到索引的映射
        Map<Character, Integer> charRank = new HashMap<>();
        for (int i = 0; i < alphaOrder.length(); i++) {
            charRank.put(alphaOrder.charAt(i), i);
        }
        
        // 读取书籍数量和书名
        int n = sc.nextInt();
        sc.nextLine(); // 消耗换行符
        List<String> books = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            books.add(sc.nextLine());
        }
        
        // 自定义比较器
        Comparator<String> customComparator = (s1, s2) -> {
            int len1 = s1.length(), len2 = s2.length();
            for (int i = 0; i < Math.min(len1, len2); i++) {
                int cmp = charRank.get(s1.charAt(i)) - charRank.get(s2.charAt(i));