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

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

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

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

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

✨ 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

数据范围

题解

我们可以根据给定的规律，直接构造出符合条件的魔法阵。

首先，我们可以发现，如果 为 的倍数或者 的倍数加 ，那么就一定存在符合条件的魔法阵。否则，无法构造出符合条件的魔法阵。

对于 为 的倍数或者 的倍数加 的情况，我们可以按照以下方式构造魔法阵：

1. 对于 为奇数且 ，令 ，。
2. 对于 为奇数且 ，令 ，。
3. 如果 为奇数，令 。

按照上述方式构造出的序列 即为符合条件的魔法阵。

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

参考代码

• 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: