题目描述

难度分:$1600$

输入$n$、$m(1 \leq n,m \leq 2 \times 10^5)$、$ta$、 $tb(1 \leq ta,tb \leq 10^9)$、$k(1 \leq k \leq n+m)$，长为$n$的严格递增数组$a(1 \leq a[i] \leq 10^9)$和长为$m$的严格递增数组$b(1 \leq b[i] \leq 10^9)$。

从A地飞往B地的航班有$n$个，第$i$个航班的起飞时刻为 $a[i]$，航行时间为$ta$。

从B地飞往C地的航班有$m$个，第$i$个航班的起飞时刻为 $b[i]$，航行时间为$tb$。
转机时间忽略不计。

你可以禁止掉其中的$k$个航班。最大化到达C的最早（最小）时刻。如果可以让人无法到达C，输出$-1$。

输入样例$1$

4 5 1 1 2
1 3 5 7
1 2 3 9 10

输出样例$1$

11

输入样例$2$

2 2 4 4 2
1 10
10 20

输出样例$2$

-1

输入样例$3$

4 3 2 3 1
1 999999998 999999999 1000000000
3 4 1000000000

输出样例$3$

1000000003

算法

双指针

首先$k \geq n$时，把所有的A飞B航班删除就肯定到不了C了，答案为$-1$。

直觉上就可以找到一个很有道理的贪心思路，就是尽可能删除A到B早的航班。假设$a[i]$是第一个未被删除的A到B航班，那么就还剩下$j=k-(i-1)$个航班可以删除，这时候会有些比较早的B到C航班是肯定赶不上的，即这些航班的起飞时间小于$a[i]+ta$。

假设最早能够赶上的B飞C航班是$b[index]$，那么就可以删除$b[index…index+j-1]$的航班。则此时的答案就是$b[index+j]+tb$，如果$index+j \gt m$，说明剩下的B飞C航班全部可以删掉，直接就到不了C了，答案为$-1$。

最后我们发现$i$越靠右，那相应的$index$也是越靠右的，所以指针不回退，双指针算法就能算出答案。

复杂度分析

时间复杂度

枚举删除A到B的航班需要遍历$i \in [1,k+1]$，在最差情况下$k$可以达到$n$，因此时间复杂度为$O(n)$。而$index$指针需要遍历$[0,m]$，时间复杂度是$O(m)$。综上，双指针算法的整体时间复杂度就是$O(n+m)$。

空间复杂度

除了输入的几个数组，仅使用了有限几个变量，因此额外空间复杂度为$O(1)$。

C++ 代码

#include <bits/stdc++.h>

using namespace std;
const int N = 200010;
int n, m, ta, tb, k, a[N], b[N];

int main() {
    scanf("%d%d%d%d%d", &n, &m, &ta, &tb, &k);
    for(int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
    }
    for(int i = 1; i <= m; i++) {
        scanf("%d", &b[i]);
    }
    if(k >= n) {
        puts("-1");
    }else {
        int ans = 0;
        // 枚举删掉A到B的航班数
        for(int i = 1, index = 0; i <= k + 1; i++) {
            int j = k - (i - 1);    // 删掉B到C的航班数
            while(index <= m && b[index] < a[i] + ta) {
                index++;
            }
            if(index + j > m) {
                ans = -1;
                break;
            }else {
                ans = max(ans, b[index + j] + tb);
            }
        }
        printf("%d\n", ans);
    }
    return 0;
}