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

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

第一题

题目

有n个物品，第i个物品的价值为ai。现在要给这些物品分组，每一组必须是个下标连续的区间。同时，每一组内的物品差距不能太大，即任意一组内物品的最大价值减去最小价值不能超过某个给定的常数k。

输入描述

第一行输入n，k(1 <= n <= 10^5, 0 <= k <= 10^9)

第二行输入n个整数a0,...,a(n-1) (0 <= ai <= 10^9)

输出描述

输出最少的分组数。

样例输入

4 1

1 3 1 4

样例输出

4

参考题解

贪心遍历

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

#include<iostream>
#include<vector>
using namespace std;
int main() {
    int n, k;
    cin >> n >> k;
    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    int ans = 0;
    for (int i = 0; i < n; ) {
        ans++;
        int mx = 0, mn = 1e9 + 1;
        int j = i;
        while (j < n) {
            int x = a[j];
            int tmx = max(mx, x);
            int tmn = min(mn, x);
            if (tmx - tmn > k) {
                break;
            }else {
                mx = tmx;
                mn = tmn;
                j++;
            }
        }
        i = j;
    }
    cout << ans << "\n";
}

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

import java.util.Scanner;
import java.util.Vector;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int k = sc.nextInt();
        Vector<Integer> a = new Vector<>(n);
        for (int i = 0; i < n; i++) {
            a.add(sc.nextInt());
        }
        
        int ans = 0;
        for (int i = 0; i < n; ) {
            ans++;
            int mx = 0, mn = Integer.MAX_VALUE;
            int j = i;
            while (j < n) {
                int x = a.get(j);
                int tmx = Math.max(mx, x);
                int tmn = Math.min(mn, x);
                if (tmx - tmn > k) {
                    break;
                } else {
                    mx = tmx;
                    mn = tmn;
                    j++;
                }
            }
            i = j;
        }
        System.out.println(ans);
        sc.close();
    }
}

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

n, k = map(int, input().split())
a = list(map(int, input().split()))

ans = 0
i = 0
while i < n:
    ans += 1
    mx, mn = 0, float('inf')
    j = i
    while j < n:
        x = a[j]
        tmx = max(mx, x)
        tmn = min(mn, x)
        if tmx - tmn > k:
            break
        else:
            mx = tmx
            mn = tmn
            j += 1
    i = j

print(ans)

第二题

题目

在一条单向道上有n辆车，每辆车的位置为pi，速度为vi(可能为负)。显然他们会发生碰撞。现在让你移除一部分车，使得剩余的车不会发生碰撞。求最少需要移除多少车？

输入描述

第一行一个整数n，表示车的数量 (1 <= n <= 10^5)

接下来n行每行两个数pi，vi，表示位置和速度。 (abs(pi), abs(vi) <= 10^9)

输出描述

输出答案。

样例输入

3

-1 -1

0 0 

1 1

样例输出

0

参考题解

可以想到，最终留下的车一定形成了一个非递减序列，因此在经位置排序后，直接求数组的最长非递减子序列即可。

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

#include<iostream>
#include<vector>
using namespace std;
int lengthOfLIS(vector<int>& nums) {
    int len = 1, n = (int)nums.size();
    if (n == 0) {
        return 0;
    }
    vector<int> d(n + 1, 0);
    d[len] = nums[0];
    for (int i = 1; i < n; ++i) {
        if (nums[i] >= d[len]) {
            d[++len] = nums[i];
        } else {
            int l = 1, r = len, pos = 0; 
            while (l <= r) {
                int mid = (l + r) >> 1;
                if (d[mid] <= nums[i]) {
                    pos = mid;
                    l = mid + 1;
                } else {
                    r = mid - 1;
                }
            }
            d[pos + 1] = nums[i];
        }
    }
    return len;
}

int main() {
    int n;
    cin >> n;
    vector<pair<int, int>> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i].first >> a[i].second;
    }

    sort(a.begin(), a.end());
    vector<int> s;
    for (int i = 0; i < n; i++) {
        s.push_back(a[i].second);
    }

    cout << n - lengthOfLIS(s) << "\n";
}

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

import