AdditionalFile5468.zip

#5468. 「eJOI2025」度假

标签: 传统 | 时间限制: 1200 ms | 内存限制: 512 MiB |

注意事项

在 LibreOJ 上，由于语言限制，目前只支持以下语言的提交：

• C++（标准为 C++ 17 及以上）

请在提交源代码前添加 #include "vacation.h"。

题目描述

题目译自 eJOI2025 Day2 T3. Vacation

Anton 和他的朋友们正计划一起去度假。他们已经选好了地点；然而，日期却难以达成一致。

所有 $N$ 位朋友都提前提交了他们计划休假的日子。朋友 $i$ 最初安排的休假时间是从第 $L_i$ 天到第 $R_i$ 天（包含首尾）。为了最大化他们能共同度过的时间，每位朋友都可以通过提前或推迟来调整自己的休假时间。具体来说，第 $i$ 位朋友可以选择一个整数 $d_i$，并将他们的休假时间调整到区间 $[L_i + d_i, R_i + d_i]$。$d_i$ 为正数表示比原计划晚休假，为负数表示提早，而 $d_i = 0$ 表示保持原计划。

朋友们知道，他们的调整会给老板带来不便。因此，他们调整休假日的总移动量不能超过某个整数 $K$。形式上，他们必须满足 $\lvert d_0 \rvert + \lvert d_1 \rvert + \dots + \lvert d_{N-1} \rvert \leq K$。

请帮助朋友们计算出，在他们优化安排日程后，所有人能共同度假的最长天数是多少。

实现细节

您应该实现 plan_vacation 函数：

 int plan_vacation(int N, std::vector<int> L, std::vector<int> R,
     long long K)

• $N$：朋友的数量
• $L$：一个包含 $N$ 个正整数的向量，其中每个元素表示该朋友最初安排的休假第一天；
• $R$：一个包含 $N$ 个正整数的向量，其中每个元素表示该朋友最初安排的休假最后一天；
• $K$：$\lvert d_0 \rvert + \lvert d_1 \rvert + \dots + \lvert d_{N-1} \rvert$ 的最大允许值。

该函数对于每个测试将被调用一次。它必须返回所有朋友能共同度假的最大天数，如果完全不可能共同度假，则返回 $0$。

示例评测程序

输入格式如下：

• 第一行包含两个整数：$N$ 和 $K$ 的值。
• 第 $2$ 行到第 $N+1$ 行：每行包含两个整数——$L_i$ 和 $R_i$。

输出格式如下：

• 第一行包含一个整数：该调用的返回值。

样例

考虑以下调用：

 plan_vacation(3, {1, 5, 2}, {3, 9, 5}, 3)

朋友们请求的休假区间如下：$[1,3], [5,9], [2,5]$。因此，朋友 $0$ 可以将他们的休假推迟 $2$ 天，朋友 $1$ 将他们的休假提前 $1$ 天，得到休假区间 $[3,5], [4,8], [2,5]$。这样，所有朋友在第 $4$ 天和第 $5$ 天都有空，共同的休假时间为 $2$ 天。可以证明，在 $K=3$ 的限制下，他们无法得到更好的结果。因此，函数应返回 $2$。

数据范围与提示

对于所有输入数据，满足：

• $1 \leq N \leq 500~000$
• $1 \leq L_i \leq R_i \leq 10^9$
• $0 \leq K \leq 10^{18}$