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

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

第一题

题目：小美的姓名统计

小美写单词喜欢横着写，她记录了若干个人的名字，但是不小心加进去了一些无关的单词。一个名字单词以大写字母开头，请你帮助她统计共有多少个人的名字。

输入描述

在一行上输入一个长度为n(1<=n<=10^5) 、且由大小写字母和空格混合构成的字符串 s代表小美的全部单词，每个单词之间使用空格间隔。除此之外，保证字符串的开头与结尾字符不为空格。

输出描述

在一行上输出一个整数，代表人名的个数。

样例输入一

ABC abc Abc

样例输出一

2

样例输入二

A A c

样例输出二

2

参考题解

判断每一个字符串的首字母是否为大写即可。

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

#include <iostream>
#include <vector>
#include <string>
#include <sstream>

int main() {
    std::string input;
    std::getline(std::cin, input);
    
    std::stringstream ss(input);
    std::string word;
    std::vector<std::string> names;

    while (ss >> word) {
        names.push_back(word);
    }

    int cnt = 0;
    for (const auto& name : names) {
        if (isupper(name[0])) cnt++;
    }

    std::cout << cnt << std::endl;
    return 0;
}

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

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String input = scanner.nextLine();
        
        String[] names = input.split("\\s+");
        int cnt = 0;

        for (String name : names) {
            if (Character.isUpperCase(name.charAt(0))) {
                cnt++;
            }
        }

        System.out.println(cnt);
        scanner.close();
    }
}

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

names = [c for c in input().split()]

cnt = 0
for name in names:
    if name[0].isupper(): cnt+=1

print(cnt)

第二题

题目：小美种树（二）

长度无限长的公路上，小美雇佣了 n 位工人来种树，每个点最多种一棵树。从左向右数，工人所站的位置为 a1,a2,...,an 。已知每位工人都会将自己所在位置的右侧一段长度的区间种满树，且每位工人的种树区间长度相同。现在小美希望公路上至少有 k棵树，为了节约成本，他希望每位工人种树的区间长度尽可能短，请你帮他求出，工人们的种树区间至少多长，才能使得公路被种上至少 k棵树。

输入描述

第一行输入两个正整数 n,k(1<=n,k<=2*10^5),分别表示工人的数量，以及小美要求树的最少数量。

第二行输入 n个正整数 a1,a2,...,an(1<=ai<=2*10^5)，表示每名工人的位置。

输出描述

在一行上输出一个整数，代表工人们最短的种树区间长度。

样例输入

3 6

1 2 5

样例输出

3

说明

每位工人种树的区间长度至少为 3。

这样以来：

第一名工人种：1,2,3 点的树。

第二名工人种：2,3,4 点的树。

第三名工人种：5,6,7点的树。

由于每个位置最多种一棵树，因此共有：1,2,3,4,5,6,7 这些点有树，满足至少 k=6棵树。

可以证明，不存在比 3 更小的答案。

参考题解

二分答案。我们来二分枚举每个人种树的区间，用一个check函数来判断种树的区间为x的适合，是否可以种k棵树？首先将数组进行排序，对于每一个人可以种的树的逻辑是：尽量往后种，在不超过之前的覆盖的前提下。bd记录的是上一次种到的边界，当前可以种的边界应该是 a+x，只要保证不会超过边界即可。

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

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

// 判断是否可以在给定的间隔范围内种下至少 k 棵树
bool check(const vector<int>& A, int x, int k) {
    int cnt = 0;
    int bd = 0; // 上一次种到的边界
    for (int a : A) {
        if (a + x > max(a, bd)) {
            cnt += (a + x) - max(a, bd);
        }
        bd = max(a + x, bd);
    }
    return cnt >= k;
}

int main() {
    int n, k;
    cin >> n >> k;

    vector<int> A(n);
    for (int i = 0; i < n; ++i) {
        cin >> A[i];
    }

    sort(A.begin(), A.end());

    int l = 0, r = 3 * 100000; // C++ 中使用更简洁的范围
    while (l < r) {
        int mid = (l + r) >> 1;
        if (check(A, mid, k)) {
            r = mid;
        } else {
            l = mid + 1;
        }
    }

    cout << r << endl;

    return 0;
}

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

import java.util.Arrays;
import java.util.Scanner;

public class Main {

    /