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

第一题

题目：城市人口

某个国家有n个城市，第i个城市的人口为ai人，如果某个城市的人口不超过其他任间一个城市人口的两倍，那么这是一个稳定的城市。国家可以对城市执行政策从而改变城市人口的数量，最少需要对几个城市执行政策，才能使得所有的城市都变得稳定。

输入描述

第一行一个整数n，表示城市的数量；

接下来一行n个整数，第i个整数表示第个城市的人口ai。

1 <= n <= 10^5

1 <= ai <= 10^9

输出描述

输出一个整数，表示最少需要修改的城市数量。

样例输入

4

1 2 3 4

样例输出

1

提示：将第一个数修改为2即可。

参考题解

贪心 + 双指针。

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

#include <iostream>
#include <algorithm>

const int MaxSize = 100004;

int numbers[MaxSize]; 
int n;

int main() {
    std::cin >> n; 
    for (int i = 1; i <= n; i++) {
        std::cin >> numbers[i]; 
    }

    std::sort(numbers + 1, numbers + n + 1);

    int minOperations = n;
    for (int left = 1, right = 1; left <= n; left++) {
        for (; right <= n && numbers[right] <= numbers[left] * 2; right++);
        minOperations = std::min(minOperations, (left - 1) + (n + 1 - right));
    }

    std::cout << minOperations << std::endl;
}

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

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

public class Main {
    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        int n = input.nextInt();
        int[] numbers = new int[n];

        for (int i = 0; i < n; i++) {
            numbers[i] = input.nextInt();
        }

        Arrays.sort(numbers);

        int minOperations = n;
        for (int left = 0, right = 0; left < n; left++) {
            while (right < n && numbers[right] <= numbers[left] * 2) {
                right++;
            }
            minOperations = Math.min(minOperations, (left) + (n - right));
        }

        System.out.println(minOperations);
    }
}

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

n = int(input())
numbers = list(map(int, input().split()))

numbers.sort()

min_operations = n
left = 0
right = 0

while left < n:
    while right < n and numbers[right] <= numbers[left] * 2:
        right += 1
    min_operations = min(min_operations, left + (n - right))
    left += 1

print(min_operations)

第二题

题目：小红选点

坐标轴上有n个点，小红希望选出其中m个点，并且这m个点两两之间距离都不超过K，求有多少种选点方案？

输入描述

一行三个整数 n,m,k，表示点的个数，选点的个数，以及两两之间距离不超过k；

接下来一行n个整数xi，表示每个点的坐标。

2 <= m <= 4

m <= n <= 10^5

1 <= xi, k <= 10^9

输出描述

输出一个整数，表示方案数，由于答案可能很大，输出答案对10^9 + 7取模的结果。

样例输入

示例一：

4 2 3

1 2 3 4

示例二：

4 2 2

1 2 3 4

样例输出

示例一：

6

提示：任选两个点都可以满足条件。

示例二：

5

参考题解

使用双指针法枚举一段可以任意取的节点，其中固定必取左端点。

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

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

typedef long long ll;

const int MaxSize = 100004;
const int MaxM = 5;
const ll Mod = 1000000007;

ll Combinations[MaxSize][MaxM];
std::vector<int> numbers;

int main() {
    int n, m, k;
    std::cin >> n >> m >> k;

    for (int i = 0; i <= n; i++) {
        Combinations[i][0] = 1;
        if (i < MaxM) {
            Combinations[i][i] = 1;
        }
        for (int j = 1; j < i && j < m; j++) {
            Combinations[i][j] = (Combinations[i - 1][j - 1] + Combinations[i - 1][j]) % Mod;
        }
    }

    numbers.resize(n + 1);
    for (int i = 1; i <= n; i++) {
        std::cin >> numbers[i];
    }

    std::sort(numbers.begin() + 1, numbers.end());

    ll ans = 0;
    for (int left = 1, right = 1; left <= n; left++) {
        while (right <= n && numbers[right] - numbers[left] <= k) {
            right++;
        }
        ans = (ans + Combinations[right - left - 1][m - 1]) % Mod;
    }

    std::cout << ans << std::endl;

    return 0;
}

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

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

public class Main {
    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        int n = input.nextInt();
        int m = input.nextInt();
        int k = input.nextInt();

        long[][] Combinations = new long[n + 1][m + 1];
        long Mod = 1000000007;

        fo