解题思路

公司要求从两类培训（业务类、管理类）各选一场，顺序任意，且每场都可在“最早开始时间或之后”任意时刻启动，持续给定时长。 设一场培训以最早时间 s 开始并持续 d，若在时刻 t(≥s) 启动，则在 t+d 结束。显然不需要把第一场延后：第一场越早结束，第二场 max(第一场结束, 第二场最早开始)+第二场时长 只会不增。

把每场的“若第一场就选它且按最早时间开始时的结束时刻”记为：

• 业务场次第 i 个：Bend[i] = Bstart[i] + Bdur[i]
• 管理场次第 j 个：Mend[j] = Mstart[j] + Mdur[j]

对固定的业务场次 i：

• 先业务后管理的最优完成时间 设 x = Bend[i]。对所有管理场次取

  min_j  ( max(x, Mstart[j]) + Mdur[j] )
  

  这是一个带释放时间的单次查询。可将管理场次按 Mstart 升序排序，预处理：

  • prefMinDur[k]：所有 Mstart < 某值 的最小 Mdur
  • sufMinEnd[k]：所有 Mstart ≥ 某值 的最小 Mend

  对查询 x，二分得到下标 idx = lower_bound(Mstart ≥ x)，答案为 min( sufMinEnd[idx], x + prefMinDur[idx-1] )（若相应集合为空则忽略该项）。 这是典型的二分 + 前缀/后缀最小值做法。

• 先管理后业务的最优完成时间 对固定 i，有

  min_j ( max(Mend[j], Bstart[i]) + Bdur[i] )
  = Bdur[i] + max( Bstart[i],  min_j Mend[j] )
  

  因为对固定 i，表达式对 Mend[j] 单调，取最小 Mend 即可。 于是仅需预处理 minMend = min_j Mend[j]，该顺序的最优为 Bdur[i] + max(Bstart[i], minMend)。

遍历所有业务场次 i，对两种顺序各取最优并取全局最小即为答案。 整体算法：

• 管理场次按开始时间排序
• 构建 prefMinDur 与 sufMinEnd
• 线性枚举业务场次并做二分查询

复杂度分析

• 预处理排序：O(m log m)
• 前缀/后缀最小：O(m)
• 每个业务场次一次二分查询：O(n log m)
• 总时间复杂度：O((n + m) log m)
• 额外空间：O(m)（存放排序后的数组与前缀/后缀最小）

在 n, m ≤ 5 * 10^4 的范围内完全可行。

代码实现

Python

import sys
from bisect import bisect_left

INF = 10**18

def query_management(x, mstart, mdur, mend, pref_min_dur, suf_min_end):
    """对给定 x = 某一业务场次的 Bend，返回 min_j max(x, Mstart[j]) + Mdur[j]"""
    m = len(mstart)
    idx = bisect_left(mstart, x)  # 第一个 Mstart >= x 的位置
    ans = INF
    if idx < m:
        ans = min(ans, suf_min_end[idx])    # 选择 Mstart >= x 的场次，直接用最小 Mend
    if idx > 0:
        ans = min(ans, x + pref_min_dur[idx - 1])  # 选择 Mstart < x 的场次，加最小 Mdur
    return ans

def solve():
    data = sys.stdin.read().strip().split()
    it = iter(map(int, data))
    n = next(it)
    bstart = [next(it) for _ in range(n)]
    bdur = [next(it) for _ in range(n)]
    m = next(it)
    mstart_raw = [next(it) for _ in range(m)]
    mdur_raw = [next(it) for _ in range(m)]

    # 管理场次按开始时间排序
    pairs = sorted(zip(mstart_raw, mdur_raw))
    mstart = [p[0] for p in pairs]
    mdur = [p[1] for p in pairs]
    mend = [mstart[i] + mdur[i] for i in range(m)]

    # 前缀最小 Mdur（用于 Mstart < x）
    pref_min_dur = [0]*m
    cur = INF
    for i in range(m):
        cur = min(cur, mdur[i])
        pref_min_dur[i] = cur

    # 后缀最小 Mend（用于 Mstart >= x）
    suf_min_end = [0]*m
    cur = INF
    for i in range(m-1, -1, -1):
        cur = min(cur, mend[i])
        suf_min_end[i] = cur

    min_mend = min(mend)  # 全局最小 Mend

    ans = INF
    for i in range(n):
        bend = bstart[i] + bdur[i]
        # 先业务后管理
        cand1 = query_management(bend, mstart, mdur, mend, pref_min_dur, suf_min_end)
        # 先管理后业务
        cand2 = bdur[i] + max(bstart[i], min_mend)
        ans = min(ans, cand1, cand2)

    print(ans)

if __name__ == "__main__":
    solve()

Java

import java.io.*;
import java.util.*;

/** ACM 风格，主类名为 Main */
public class Main {
    static final long INF = (long)1e18;

    // 在排序后的管理数组上做查询：min_j max(x, Mstart[j]) + Mdur[j]
    static long queryManagement(long x, int[] mstart, int[] mdur, long[] mend,
                                long[] prefMinDur, long[] sufMinEnd) {
        int m = mstart.length;
        int idx = lowerBound(mstart, (int)x); // 第一个 Mstart >= x 的位置
        long ans = INF;
        if (idx < m) ans = Math.min(ans, sufMinEnd[idx]);      // 选择 Mstart >= x
        if (idx > 0) ans = Math.min(ans, x + prefMinDur[idx-1]); // 选择 Mstart < x
        return ans;
    }

    // 标准 lower_bound
    static int lowerBound(int[] a, int key) {
        int l = 0, r = a.length;
        while (l < r) {
            int mid = (l + r) >>> 1;
            if (a[mid] >= key) r = mid;
            else l = mid + 1;
        }
        return l;
    }

    public static void main(String[] args) throws Exception {
        // 由于数据量较大，使用 BufferedReader + StringTokenizer
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        int n = Integer.parseInt(br.readLine().trim());
        int[] bstart = new int[n];
        int[] bdur = new int[n];

        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) bstart[i] = Integer.parseInt(st.nextToken());

        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) bdur[i] = Integer.parseInt(st.nextToken());

        int m = Integer.parseInt(br.readLine().trim());
        int[] mstartRaw = new int[m];
        int[] mdurRaw = new int[m];

        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < m; i++) mstartRaw[i] = Integer.parseInt(st.nextToken());

        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < m; i++) mdurRaw[i] = Integer.parseInt(st.nextToken());

        // 管理场次按开始时间排序
        int[][] pair = new int[m][2];
        for (int i = 0; i < m; i++) { pair[i][0] = mstartRaw[i]; pair[i][1] = mdurRaw[i]; }
        Arrays.sort(pair, new Comparator<int[]>() {
            public int compare(int[] a, int[] b) { return Integer.compare(a[0], b[0]); }
        });
        int[] mstart = new int[m];
        int[] mdur = new int[m];
        for (int i = 0; i < m; i++) { mstart[i] = pair[i][0]; mdur[i] = pair[i][1]; }

        long[] mend = new long[m];
        for (int i = 0; i < m; i++) mend[i] = (long)mstart[i] + mdur[i];

        long[] prefMinDur = new long[m];
        long cur = INF;
        for (int i = 0; i < m; i++) {
            cur = Math.min(cur, (long)mdur[i]);
            prefMinDur[i] = cur;
        }

        long[] sufMinEnd = new long[m];
        cur = INF;
        for (int i = m - 1; i >= 0; i--) {
            cur = Math.min(cur, mend[i]);
            sufMinEnd[i] = cur;
        }

        long minMend = INF;
        for (int i = 0; i < m; i++) minMend = Math.min(minMend, mend[i]);

        long ans = INF;
        for (int i = 0; i < n; i++) {
            long bend = (long)bstart[i] + bdur[i];
            long cand1 = queryManagement(bend, mstart, mdur, mend, prefMinDur, sufMinEnd); // 先业务后管理
            long cand2 = (long)bdur[i] + Math.max(bstart[i], minMend);                     // 先管理后业务
            ans = Math.min(ans, Math.min(cand1, cand2));
        }

        System.out.println(ans);
    }
}

C++

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const long long INF = (long long)1e18;

// 在排序后的管理数组上查询：min_j max(x, Mstart[j]) + Mdur[j]
long long queryManagement(long long x,
                          const vector<int>& mstart,
                          const vector<int>& mdur,
                          const vector<long long>& mend,
                          const vector<long long>& prefMinDur,
                          const vector<long long>& sufMinEnd) {
    int m = (int)mstart.size();
    int idx = lower_bound(mstart.begin(), mstart.end(), (int)x) - mstart.begin();
    long long ans = INF;
    if (idx < m) ans = min(ans, sufMinEnd[idx]);         // 选 Mstart >= x 的
    if (idx > 0)  ans = min(ans, x + prefMinDur[idx-1]); // 选 Mstart < x 的
    return ans;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n; 
    if (!(cin >> n)) return 0;
    vector<int> bstart(n), bdur(n);
    for (int i = 0; i < n; ++i) cin >> bstart[i];
    for (int i = 0; i < n; ++i) cin >> bdur[i];

    int m; cin >> m;
    vector<int> mstartRaw(m), mdurRaw(m);
    for (int i = 0; i < m; ++i) cin >> mstartRaw[i];
    for (int i = 0; i < m; ++i) cin >> mdurRaw[i];

    // 管理场次按开始时间排序
    vector<pair<int,int>> v(m);
    for (int i = 0; i < m; ++i) v[i] = {mstartRaw[i], mdurRaw[i]};
    sort(v.begin(), v.end());
    vector<int> mstart(m), mdur(m);
    for (int i = 0; i < m; ++i) { mstart[i] = v[i].first; mdur[i] = v[i].second; }

    vector<long long> mend(m);
    for (int i = 0; i < m; ++i) mend[i] = (long long)mstart[i] + mdur[i];

    // 前缀最小 Mdur
    vector<long long> prefMinDur(m);
    long long cur = INF;
    for (int i = 0; i < m; ++i) {
        cur = min(cur, (long long)mdur[i]);
        prefMinDur[i] = cur;
    }
    // 后缀最小 Mend
    vector<long long> sufMinEnd(m);
    cur = INF;
    for (int i = m-1; i >= 0; --i) {
        cur = min(cur, mend[i]);
        sufMinEnd[i] = cur;
    }

    long long minMend = INF;
    for (int i = 0; i < m; ++i) minMend = min(minMend, mend[i]);

    long long ans = INF;
    for (int i = 0; i < n; ++i) {
        long long bend = (long long)bstart[i] + bdur[i];
        long long cand1 = queryManagement(bend, mstart, mdur, mend, prefMinDur, sufMinEnd); // 先业务后管理
        long long cand2 = (long long)bdur[i] + max((long long)bstart[i], minMend);          // 先管理后业务
        ans = min(ans, min(cand1, cand2));
    }

    cout << ans << "\n";
    return 0;
}

题目内容

公司为提升员工综合能力，提供了两种不同类别的主题培训:业务类主题培训和管理类主题培训，并要求每位员工必须从这两类培训中各选择恰好一门参加，具体顺序可自由安排。

业务类主题培训有多个场次，其中$businessstartTime[i]$表示第$i$个业务类培训场次的最早可开始时间， $businessDuration[i]$表示该场次的持续时长。

管理类主题培训也有多个场次，其中$managementstartTime[j]$表示第$j$个管理类培训场次的最早可开始时间，$managementDuration[j]$表示该场次的持续时长。

培训的具体规则如下:

1.员工可在培训场次的最早开始时间或之后的任意时间开始参加该场次。

2.若某场培训在时间$t$开始，那么它将在$t$+该场次持续时长时结束。

3.完成一个培训后，员工可以立即参加下一个培训(若下一个已到最早开始时间)，也可等待下一个到最早 开始时间后再参加。

请编写代码返回员工完成这两门培训的最早可能结束时间。

输入描述

第一行输入一个整数，表示$businessStartTime.length$。

第二行输入$businessstartTime.length$个整数，表示$businessstartTime$

第三行输入$businessstartTime.length$个整数，表示$businessDuration$

第四行输入一个整数，表示$managementstartTime.length$。

第五行输入$managementstartTime.length$个整数，表示$managementstartTime$。

第六行输入$managementstartTime .length$个整数，表示$managementDuration$

输出描述

输出一个整数，表示员工完成这两门培训的最早可能结束时间。

样例1

输入

2
2 8
4 1
1 
6 
3

输出

9

提示

$1 <= n, m <=5* 10^4$

$businessStartTime.length==businessDuration.length == n$

$managementstartTime.length==managementDuration.length == m$

$1 <= businessStartTime[i]，businessDuration[i]，managementstartTime[j]，managementDuration[j] <=10^5$