笔试时间：2023年9月13日 秋招

第一题

题目：快递中转站

快递公司有一个业务要求，所有当天下发到快递中转站的快递，最迟在第二天送达用户手中。假设已经知道接下来n天每天下发到快递中转站的快递重量。快递中转站负责人需要使用快递运输车运输给用户，每一辆运输车最大只能装k重量的快递。每天可以出车多次，也可以不出车，也不要求运输车装满。当天下发到快递中转站的快递，最晚留到第二天就要运输走送给用户。快递中转站负责人希望出车次数最少，完成接下来n天的快递运输。

解答要求：时间限制: C/C++ 1000ms,其他语言: 2000ms内存限制: C/C++256MB其他语言: 512MB

输入描述

输入第一行包含两个整数n(1<= n<=200000)，k(1<=k<=100000000)

第二行包含n个整数ai，表示第i天下发到快递中转站的快递重量。

输出描述

输出最少需要的出车次数。

样例输入

3 2

3 2 1

样例输出

3

说明

第一天的快递出车一次送走2个重量，留1个重量到第二天

第二天送走第一天留下的1个重量和当前的1个重量，留1个重量到第三天送走。

参考题解

模拟题。

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

#include <iostream>
#include <vector>

using namespace std;

int main() {
    long long totalNumbers, divisor;
    cin >> totalNumbers >> divisor;

    vector<int> numbers(totalNumbers, 0);
    for (int i = 0; i < totalNumbers; i++) {
        cin >> numbers[i];
    }

    long long totalOperations = 0;
    long long remainder = 0;

    for (int i = 0; i < totalNumbers; i++) {
        long long currentSum = numbers[i] + remainder;
        long long divisionResult = currentSum / divisor;
        long long newRemainder = currentSum % divisor;

        if (divisionResult == 0 && remainder != 0) {
            divisionResult++;
            newRemainder = 0;
        }

        totalOperations += divisionResult;
        remainder = newRemainder;
    }

    if (remainder != 0) {
        totalOperations++;
    }

    cout << totalOperations << endl;

    return 0;
}

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

import java.util.Scanner;

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

        long[] numbers = new long[(int) totalNumbers];
        for (int i = 0; i < totalNumbers; i++) {
            numbers[i] = scanner.nextLong();
        }

        long totalOperations = 0;
        long remainder = 0;

        for (int i = 0; i < totalNumbers; i++) {
            long currentSum = numbers[i] + remainder;
            long divisionResult = currentSum / divisor;
            long newRemainder = currentSum % divisor;

            if (divisionResult == 0 && remainder != 0) {
                divisionResult++;
                newRemainder = 0;
            }

            totalOperations += divisionResult;
            remainder = newRemainder;
        }

        if (remainder != 0) {
            totalOperations++;
        }

        System.out.println(totalOperations);
    }
}

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

total_numbers, divisor = map(int, input().split())
numbers = list(map(int, input().split()))

total_operations = 0
remainder = 0

for num in numbers:
    current_sum = num + remainder
    division_result = current_sum // divisor
    new_remainder = current_sum % divisor

    if division_result == 0 and remainder != 0:
        division_result += 1
        new_remainder = 0

    total_operations += division_result
    remainder = new_remainder

if remainder != 0:
    total_operations += 1

print(total_operations)

第二题

题目：互通设备集

局一局域网内的设备可以相互发现，具备直连路由的两个设备可以互通。假定设备A和B互通，B和C互通，那么可以将B作为中心设备，通过多跳路由策略使设备A和C互通。这样，A、B、C三个设备就组成了一个互通设备集。其中，互通设备集包括以下几种情况:

1、直接互通的多个设备；

2、通过多跳路由第略间接互通的多个设备；

3、没有任何互通关系的单个设备现给出某一局域网内的设备总数以及具备直接互通关系的设备。

请计算该局域网内的互通设备集有多少个？

输入描述

第一行: 某一局域网内的设备总数M，32位有符号整数表示。1<= M<=200

第二行:具备直接互通关系的数量N，32位有符号整数表示。0<= N<200

第三行到第N+2行: 每行两个有符号32位整数，分别表示具备直接互通关系的两个设备的编号，用空格隔开。每个设备具有唯一的编号，0<设备编号< M

输出描述

互通设备集的数量，32位有符号整数表示。

样例输入

3

2

0 1

0 2

样例输出

1

说明

编号0和1以及编号0和2的设备直接互通，编号1和2的设备可通过编号0的设备建立互通关系，互通设备集可合并为1个。

参考题解

并查集，参考岛屿解法。

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

#include <iostream>
#include <vector>

using namespace std;

vector<int> parent;

void initialize(int n) {
    parent.assign(n, 0);
    for (int i = 0; i < n; i++) {
        parent[i] = i;
    }
}

int findSet(int x) {
    return (x == parent[x]) ? x : (parent[x] = findSet(parent[x]));
}

void unionSets(int x, int y) {
    parent[findSet(x)] = findSet(y);
}

int main() {
    int m, n;
    cin >> m >> n;
    initialize(m);

    int u, v;
    for (int i = 0; i < n; i++) {
        cin >> u >> v;
        unionSets(u, v);
    }

    int numDisjointSets = 0;
    for (int i = 0; i < m; i++) {
        if (findSet(i) == i) {
            numDisjointSets++;
        }
    }

    cout << numDisjointSets << endl;

    return 0;
}

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

import java.util.Scanner;

public class Main {
    static int[] parent;

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int m = scanner.nextInt();
        int n = scanner.nextInt();
        initialize(m);

        int u, v;
        for (int i = 0; i < n; i++) {
            u = scanner.nextInt();
            v = scanner.nextInt();
            unionSets(u, v);
        }

        int numDisjointSets = 0;
        for (int i = 0; i < m; i++) {
            if (findSet(i) == i) {
                numDisjointSets++;
            }
        }

        System.out.println(numDisjointSets);