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

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

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

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

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

🚂 01.K小姐的礼物清单

问题描述

K小姐正在准备送给朋友们的礼物，她有一个长度为 的礼物清单 ，其中 表示第 个朋友希望收到的礼物价格。为了让朋友们都感到满意，K小姐决定再准备一个长度为 的清单 ，其中 表示第 个朋友实际收到的礼物价格。

K小姐希望清单 满足以下条件：

1. 每个礼物的价格都是 范围内的整数。
2. 所有礼物的价格互不相同。
3. 对于每个朋友 ，都有 。

请你帮助K小姐构造出一个满足条件的礼物清单 。

输入格式

第一行包含一个整数 ，表示礼物清单的长度。

第二行包含 个整数，表示礼物清单 ，其中第 个整数 表示第 个朋友希望收到的礼物价格。

输出格式

输出一行，包含 个整数，表示构造出的礼物清单 ，其中第 个整数 表示第 个朋友实际收到的礼物价格。

样例输入

5
1 2 3 4 5

样例输出

1 2 3 4 5

数据范围

题解

本题可以按照输入的顺序依次构造清单 。对于第 个朋友，我们可以先计算出一个满足条件 的最小正整数 ，然后检查 是否已经在之前的礼物价格中出现过。如果出现过，就将 增加 ，直到找到一个未出现过的且不超过 的礼物价格。

具体步骤如下：

1. 遍历清单 的每个元素 。
2. 计算 ，如果 ，则将 加上 。
3. 如果 已经在之前的礼物价格中出现过，就将 增加 ，直到找到一个未出现过的且不超过 的礼物价格。
4. 将 加入清单 ，并将 标记为已出现。
5. 输出构造出的清单 。

时间复杂度为 ，空间复杂度为 。

参考代码

• Python

def solve():
    n = int(input())
    A = list(map(int, input().split()))
    B = []
    used = set()
    
    for i, a in enumerate(A, start=1):
        b = i - a % i
        if b < 1:
            b += i
        while b in used and b <= 10**9:
            b += i
        B.append(b)
        used.add(b)
    
    print(*B)

solve()

• 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];
        for (int i = 0; i < n; i++) {
            A[i] = sc.nextInt();
        }
        
        int[] B = new int[n];
        Set<Integer> used = new HashSet<>();
        
        for (int i = 0; i < n; i++) {
            int b = i + 1 - A[i] % (i + 1);
            if (b < 1) {
                b += i + 1;
            }
            while (used.contains(b) && b <= 1000000000) {
                b += i + 1;
            }
            B[i] = b;
            used.add(b);
        }
        
        for (int b : B) {
            System.out.print(b + " ");
        }
    }
}

• Cpp

#include <iostream>
#include <vector>
#include <unordered_set>
using namespace std;

void solve() {
    int n;
    cin >> n;
    vector<int> A(n);
    for (int i = 0; i < n; i++) {
        cin >> A[i];
    }
    
    vector<int> B;
    unordered_set<int> used;
    
    for (int i = 0; i < n; i++) {
        int b = i + 1 - A[i] % (i + 1);
        if (b < 1) {
            b += i + 1;
        }
        while (used.count(b) && b <= 1e9) {
            b += i + 1;
        }
        B.push_back(b);
        used.insert(b);
    }
    
    for (int b : B) {
        cout << b << " ";
    }
}

int main() {
    solve();
    return 0;
}

🧇 02.K小姐的蛋糕店

问题描述

K小姐经营着一家蛋糕店，她的蛋糕店有 种口味的蛋糕。这 种口味的蛋糕在 A 工厂和 B 工厂都有生产。

对于每种口味的蛋糕，如果 A 工厂生产的口感值为 ，价格为 ；B 工厂生产的口感值为 ，价格为 。K小姐会比较两个工厂生产的同一口味蛋糕，如果 且 ，那么她会选择从 A 工厂进货这种口味的蛋糕；如果 且 ，那么她会选择从 B 工厂进货这种口味的蛋糕；如果两个工厂生产的蛋糕口感值和价格都相同，或者一个工厂口感值更高但价格也更高，那么K小姐就不会选择进货这种口味的蛋糕。

现在给定 种口味蛋糕在两个工厂的口感值和价格，请问K小姐最终会选择进货多少种口味的蛋糕？

输入格式

第一行输入一个整数 ，表示蛋糕的口味数量。

第二行输入 个整数，分别表示 ，即 A 工厂生产的 种口味蛋糕的口感值。

第三行输入 个整数，分别表示 ，即 B 工厂生产的 种口味蛋糕的口感值。

第四行输入 个整数，分别表示 ，即 A 工厂生产的 种口味蛋糕的价格。

第五行输入 个整数，分别表示 ，即 B 工厂生产的 种口味蛋糕的价格。

输出格式

输出一个整数，表示K小姐最终选择进货的蛋糕口味数量。

样例输入

5
1 2 3 4 5
5 4 3 2 1
10 9 8 7 6
6 7 8 9 10

样例输出

4

数据范围

题解

本题可以通过简单的比较来解决。对于每种口味的蛋糕，我们比较 A 工厂和 B 工厂生产的蛋糕的口感值和价格，如果满足以下两个条件之一，就选择进货该口味的蛋糕：

1. A 工厂生产的蛋糕口感值更高，且价格更低，即 且 。
2. B 工厂生产的蛋糕口感值更高，且价格更低，即 且 。

最后统计满足条件的蛋糕口味数量即可。

时间复杂度：，其中 是蛋糕的口味数量。 空间复杂度：。

参考代码

• Python

n = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = list(map(int, input().split()))
D = list(map(int, input().split()))

count = 0
for i in range(n):
    if A[i] > B[i] and C[i] < D[i]:
        count += 1
    elif B[i] > A[i] and D[i] < C[i]:
        count += 1

print(count)

• Java

import java.util.Scanner;

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];
        int[] C = new int[n];
        int[] D = 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()