笔试时间：2024年04月02日

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

第一题

题目：最长上课时间

教授每天会有课程安排，第i个课程开始时间设为A[i],结束时间为B[i],课程之间需要有一定时间休息，记为x，给定A, B, x,找出一种课程安排，使得教授上课时长最长。

输入描述

第一行:休息时间x

第二行:课程数n (1 <= n <= 10^5)

第三行:n个课程的开始时间,空格隔开

第四行:n个课程的结束时间,空格隔开

输出描述

一个数字。

样例输入

2

3

1 3 6

3 5 10

样例输出

6

参考题解

动态规划。

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

#include <bits/stdc++.h>

#define x first
#define y second

using namespace std;

const int N = 1e5 + 10;

typedef pair<int, int> pii;

long long n, x, f[N];
pii a[N];

int main()
{
    cin >> x >> n;
    for(int i = 1; i <= n; i ++)
        cin >> a[i].x;
        
    for(int i = 1; i <= n; i ++)
        cin >> a[i].y;
    
    f[1] = a[1].y - a[1].x;
    
    for(int i = 2; i <= n; i ++)
    {
        f[i] = max(f[i - 1], a[i].y - a[i].x);
        
        int l = 0, r = i, mid;
        while(l + 1 != r)
        {
            mid = l + r >> 1;
            if((a[mid].y + x) <= a[i].x) l = mid;
            else r = mid;
        }
     
        if(l != 0)
        {
            f[i] = max(f[i], f[l] + (a[i].y - a[i].x));
        }
    }
    
    cout << f[n] << endl;
    
    return 0;
}

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

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

public class Main {
    static final int N = 100010;
    static long n, x;
    static long[] f = new long[N];
    static Pair[] a = new Pair[N];

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        
        x = sc.nextLong();
        n = sc.nextLong();
        
        for (int i = 1; i <= n; i++) {
            a[i] = new Pair(sc.nextInt(), 0);
        }
        
        for (int i = 1; i <= n; i++) {
            a[i].y = sc.nextInt();
        }
        
        f[1] = a[1].y - a[1].x;
        
        for (int i = 2; i <= n; i++) {
            f[i] = Math.max(f[i - 1], a[i].y - a[i].x);
            
            int l = 0, r = i, mid;
            while (l + 1 != r) {
                mid = (l + r) >> 1;
                if ((a[mid].y + x) <= a[i].x) l = mid;
                else r = mid;
            }
         
            if (l != 0) {
                f[i] = Math.max(f[i], f[l] + (a[i].y - a[i].x));
            }
        }
        
        System.out.println(f[(int)n]);
        
        sc.close();
    }

    static class Pair {
        int x, y;
        Pair(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }
}

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

N = 100010

n = 0
x = 0
f = [0] * N
a = [None]