笔试时间：2024年09月08日 秋招

历史笔试传送门：2023秋招笔试合集

第一题

题目

小苯有n个钱包，其中第i个钱包装了ai元，他每天都会恰好使用一个钱包中的钱去购物，尽可能多地购买 一种单价为k元的物品，日复一日，直到所有钱包中的钱都分别买不起此物品。 在小苯在开始日复一日地购物前，可以向任意一些钱包中再加入一些钱，但总共加入的钱数不超过m. 现在小苯想知道，如果自己以最优方案向钱包中加钱，那么最多可以购买多少件此物品。

输入描述

第一行输入三个整数n,k和m(1≤n≤10^5;1≤k≤10^9；0≤m≤10^14)表示小苯的钱包个数，要购买的物品单价，以及小苯最多可以提前加入钱包中的钱。

第二行输入n个正整数a1,a2,...,an(1≤ai≤10^9)表示小苯每个钱包中的钱数。

输出描述

在一行上输出一个整数，表示小苯最多可以购买的此物品数量。

样例输入

5 3 2

4 4 3 1 2

样例输出

4

参考题解

初始购买能力：首先，对于每个钱包 a[i]，可以用 a[i] / k 计算出该钱包当前可以购买的商品数量，累加得到总共能购买的商品数。然后，计算每个钱包中还差多少钱可以再购买一个商品，差值为 k - (a[i] % k)，如果这个差值是 0 说明已经整除，不需要补钱。补钱优化：将每个钱包补足到下一个能够购买商品的差值存入一个数组 a 中，并对该数组进行排序，优先对差值小的钱包补足。然后，对于每一个差值，判断当前剩余的可补金额 m 是否足够补足。如果足够补足，则购买数量加 1，同时减少 m 的余额。这一过程可以保证在不超过 m 元的限制下，补钱的收益最大化。剩余的钱直接购买：如果 m 还有剩余，直接用剩余的钱再尽可能购买一些商品，也就是计算 m / k，将其加到总购买数量中。

C++：[此代码未进行大量数据的测试，仅供参考]

#include <bits/stdc++.h>
using namespace std;
int main()
{
    long long n, m, k;
    cin >> n >> k >> m;
    vector<long long> a(n);
    long long sum = 0;
    for (long long i = 0; i < n; i++)
    {
        long long x;
        cin >> x;
        sum += x / k;
        a[i] = k - x % k;
    }
    sort(a.begin(), a.end());
    for (long long i = 0; i < n; i++)
    {
        if (m >= a[i])
        {
            sum++;
            m -= a[i];
        }
        else
        {
            break;
        }
    }
    sum += m / k;
    cout << sum << endl;
}

Java：[此代码未进行大量数据的测试，仅供参考]

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        long n = scanner.nextLong();
        long k = scanner.nextLong();
        long m = scanner.nextLong();

        long[] a = new long[(int) n];
        long sum = 0;

        for (long i = 0; i < n; i++) {
            long x = scanner.nextLong();
            sum += x / k;
            a[(int) i] = k - x % k;
        }

        Arrays.sort(a);

        for (long i = 0; i < n; i++) {
            if (m >= a[(int) i]) {
                sum++;
                m -= a[(int) i];
            } else {
                break;
            }
        }

        sum += m / k;
        System.out.println(sum);
        scanner.close();
    }
}

Python：[此代码未进行大量数据的测试，仅供参考]

n, k, m = map(int, input().split())
a = []
sum = 0

for _ in range(n):
    x = int(input())
    sum += x // k
    a.append(k - x % k)

a.sort()

for i in range(n):
    if m >= a[i]:
        sum += 1
        m -= a[i]
    else:
        break

sum += m // k
print(sum)

第二题

题目

小红有一个长度为2×n-1的数组，每次可以选择其中n个数，将这n个数取反，小红想知道经过若干次操作之后，所有数组元素之和的最大是多少。

输入描述

第一行一个整数n，数组长度为2×n-1

第二行2×n-1个整数，表示数组元素。

1≤n≤10^5； -10^9≤ai≤10^9

输出描述

输出一个整数，表示所有数组元素之和的最大值。

样例输入

3

1 2 3 -4 5

样例输出

15

说明

先选择前三个元素取反，再选择后三个元素取反，数组元素之和最大为15。

参考题解

可以通过贪心算法来解决。目标是通过对数组进行若干次操作，使得数组元素的和尽可能最大化。取绝对值排序：我们可以将数组的所有元素取绝对值，并根据绝对值大小进行排序。因为每次可以将 nnn 个数取反，排序后我们优先将较大的负数取反，使其变为正数，这样能使总和增大。贪心策略：考虑两种情况：如果数组中负数的个数为偶数，说明可以直接将所有负数变为正数；如果负数的个数为奇数，则可以把最小的正数或负数（绝对值最小的那个数）保留为负数，以保证操作次数的限制。

C++：[此代码未进行大量数据的测试，仅供参考]

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    cin >> n; // 输入 n
    int len = 2 * n - 1; // 数组长度为 2 * n - 1
    vector<int> arr(len);
    
    // 输入数组元素
    for (int i = 0; i < len; i++) {
        cin >> arr[i];
    }
    
    // 绝对值排序
    sort(arr.begin(), arr.end(), [](int a, int b) {
        return abs(a) > abs(b);
    });
    
    // 贪心：逐个考虑元素
    long long sum = 0;
    int negative_count = 0;
    for (int i = 0; i < len; i++) {
        if (arr[i] < 0) {
            negative_count++;
        }
        sum += abs(arr[i]);
    }
    
    // 如果负数个数为奇数，则减去最小绝对值的两倍
    if (negative_count % 2 == 1) {
        sum -= 2 * abs(arr[len - 1]);
    }
    
    // 输出结果
    cout << sum << endl;

    return 0;
}

Java：[此代码未进行大量数据的测试，仅供参考]

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int len = 2 * n - 1;
        int[] arr = new int[len];

        // 输入数组元素
        for (int i = 0; i < len; i++) {
            arr[i] = scanner.nextInt();
        }

        // 绝对值排序
        Arrays.sort(arr, (a, b) -> Integer.compare(Math.abs(b), Math.abs(a)));

        // 贪心算法：逐个考虑元素
        long sum = 0;
        int negativeCount = 0;

        for (int i = 0; i < len; i++) {
            if (arr[i] < 0) {
                negativeCount++;
            }
            sum += Math.abs(arr[i]);
        }

        // 如果负数个数为奇数，则减去最小绝对值的两倍
        if (negativeCount % 2 == 1) {
            sum -= 2 * Math.abs(arr[len - 1]);
        }

        // 输出结果
        System.out.println(sum);
        scanner.close();
    }
}

Python：[此代码未进行大量数据的测试，仅供参考]

n = int(input())
length = 2 * n - 1
arr = list(map(int, input().split()))

# 绝对值排序
arr.sort(key=lambda x: abs(x), reverse=True)

# 贪心算法：逐个考虑元素
sum_value = 0
negative_count = 0

for i in range(length):
    if arr[i] < 0:
        negative_count += 1
    sum_value += abs(arr[i])

# 如果负数个数为奇数，则减去最小绝对值的两倍
if negative_count % 2 == 1:
    sum_value -= 2 * abs(arr[length - 1])

# 输出结果
print(sum_value)

第三题

题目

小红有一棵n个点的树，其中1号点是根。每个点有一个权值ai。如果满足任意节点的权值大于等于其子节点的权值和，那么这棵树就是一棵奇妙树。小红每次操作可以选择一个点，将其权值加一。请问小红最少需要多少次操作，才能使这棵树变成一棵奇妙树。

输入描述

第一行一个整数n，表示树的节点数。

第二行n个整数ai,表示每个点的权值。

接下来n-1行，每行两个整数u和v,表示u和v之间有一条边。

2≤n≤10^5

1≤ai≤10^9

1≤u,v≤n

输出描述

输出一个整数，表示最少需要多少次操作。

输出描述 返回一个数字表示结果。

样例输入

3

1 2 3

1 2

1 3

样例输出

4

参考题解

通过DFS来遍历树的每一个节点（树形dfs），并在遍历的过程中计算每个节点的子节点权值和。我们需要最少次数的操作将这棵树变成满足“每个节点的权值大于等于其子节点权值和”的奇妙树。从根节点开始深度优先遍历。对于每个节点，计算其子节点权值的总和 sum，如果子节点权值总和超过当前节点的权值，就记录需要增加的次数。最后输出累积的操作次数。

C++：[此代码未进行大量数据的测试，仅供参考]

#include <bits/stdc++.h>
using namespace std;
vector<int> e[200005];
long long a[200005];
long long ans = 0;
long long dfs(int u, int fa)
{
    long long sum = 0;
    for (int v : e[u])
    {
        if (v == fa)
            continue;
        sum += dfs(v, u);
    }
    if (sum > a[u])
    {
        ans += sum - a[u];
    }
    return max(sum, a[u]);
}
int main()
{
    int n;
    cin >> n;