#5468. 「eJOI2025」度假 题解

问题分析

有 $N$ 个区间 $[L_i, R_i]$，每个区间可以平移 $d_i$ 变成 $[L_i+d_i, R_i+d_i]$，要求 $\sum |d_i| \leq K$，求所有区间交的最大长度。

关键观察

1. 问题转化：设最终所有区间交为 $[x, x+len]$，则第 $i$ 个区间需要移动的最小距离为：

   • 如果 $[L_i, R_i]$ 完全在 $[x, x+len]$ 左边：需要 $|x - R_i|$
   • 如果 $[L_i, R_i]$ 完全在 $[x, x+len]$ 右边：需要 $|L_i - (x+len)|$
   • 如果相交：需要移动距离为 $0$

2. 二分答案：可以二分最终的交集长度 $len$，检查是否存在 $x$ 使得总移动距离 $\leq K$

算法思路

1. 二分交集长度

设最终交集为 $[x, x+len]$，对每个区间 $[L_i, R_i]$：

• 如果 $R_i < x$，需要移动 $x - R_i$
• 如果 $L_i > x+len$，需要移动 $L_i - (x+len)$
• 否则不需要移动

2. 检查可行性

对于固定的 $len$，需要找到 $x$ 使得总移动距离最小。可以证明代价函数是凸的，可以用三分法找最小值。

3. 优化计算

对于固定的 $x$，总代价为：

$$\sum \max(0, x - R_i) + \sum \max(0, L_i - (x+len)) $$

这可以通过排序后使用前缀和快速计算。

代码实现

#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;

typedef long long ll;

bool check(int len, int N, vector<int>& L, vector<int>& R, ll K) {
    // 预处理排序
    vector<int> sorted_L = L, sorted_R = R;
    sort(sorted_L.begin(), sorted_L.end());
    sort(sorted_R.begin(), sorted_R.end());
    
    // 计算前缀和
    vector<ll> prefix_L(N+1), prefix_R(N+1);
    for (int i = 0; i < N; i++) {
        prefix_L[i+1] = prefix_L[i] + sorted_L[i];
        prefix_R[i+1] = prefix_R[i] + sorted_R[i];
    }
    
    // 三分法找最小代价
    auto calc_cost = [&](ll x) {
        // 计算 R_i < x 的部分
        int idx1 = lower_bound(sorted_R.begin(), sorted_R.end(), x) - sorted_R.begin();
        ll cost1 = x * idx1 - prefix_R[idx1];
        
        // 计算 L_i > x+len 的部分  
        ll right_bound = x + len;
        int idx2 = upper_bound(sorted_L.begin(), sorted_L.end(), right_bound) - sorted_L.begin();
        ll cost2 = (prefix_L[N] - prefix_L[idx2]) - right_bound * (N - idx2);
        
        return cost1 + cost2;
    };
    
    // 三分搜索范围
    ll left = 1, right = 1e18;  // 扩大搜索范围
    while (right - left > 3) {
        ll mid1 = left + (right - left) / 3;
        ll mid2 = right - (right - left) / 3;
        ll cost1 = calc_cost(mid1);
        ll cost2 = calc_cost(mid2);
        if (cost1 <= K || cost2 <= K) return true;
        if (cost1 < cost2) right = mid2 - 1;
        else left = mid1 + 1;
    }
    
    // 检查剩余点
    for (ll x = left; x <= right; x++) {
        if (calc_cost(x) <= K) return true;
    }
    return false;
}

int plan_vacation(int N, vector<int> L, vector<int> R, ll K) {
    // 特判：如果K=0，直接计算原始区间的最大交集
    if (K == 0) {
        int maxL = *max_element(L.begin(), L.end());
        int minR = *min_element(R.begin(), R.end());
        return max(0, minR - maxL + 1);
    }
    
    // 二分答案：交集长度
    int left = 0, right = 1e9, ans = 0;
    while (left <= right) {
        int mid = (left + right) / 2;
        if (check(mid, N, L, R, K)) {
            ans = mid;
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    return ans;
}

复杂度分析

• 二分答案：$O(\log(10^9))$ 次
• 可行性检查：$O(N \log N)$ 排序预处理，三分 $O(\log(10^{18}))$ 次，每次 $O(\log N)$ 二分
• 总复杂度：$O(N \log N \log(10^9) \log(10^{18}))$，在 $N=5\times10^5$ 时可接受

样例验证

样例

N=3, L={1,5,2}, R={3,9,5}, K=3

二分过程：
len=0: 可行（代价0）
len=1: 可行（代价最小为1）
len=2: 可行（代价最小为3）  
len=3: 不可行（代价最小>3）

返回结果：2

优化点

1. 预处理排序：避免每次检查重复排序
2. 前缀和：快速计算区间和
3. 三分法：利用凸性快速找到最小值
4. 边界处理：注意整数范围和边界情况

总结

本题通过二分答案+三分搜索，将复杂的最优化问题转化为可行性检查问题。利用区间的有序性和前缀和优化，在合理时间内解决了大规模数据的最优安排问题。