「POI2018 R1」律师 Lawyers 题解

问题分析

我们需要从 $n$ 个区间（律师的空闲时间段）中选择 $k$ 个，使得它们的交集长度最大。

关键观察：

• 最优解中，交集的左端点一定是某个区间的左端点
• 最优解中，交集的右端点一定是某个区间的右端点

算法思路

1. 基本思路

对于任意 $k$ 个区间 $[l_1, r_1], [l_2, r_2], \dots, [l_k, r_k]$，它们的交集为：

$$[\max(l_1, l_2, \dots, l_k), \min(r_1, r_2, \dots, r_k)] $$

交集长度为 $\max(0, \min(r_i) - \max(l_i))$。

2. 核心算法

我们可以使用双指针 + 数据结构的方法：

1. 按左端点排序：将所有区间按左端点从小到大排序
2. 使用数据结构维护右端点：当固定左端点时，我们需要找到当前包含的区间中第 $k$ 小的右端点
3. 滑动窗口：维护一个包含至少 $k$ 个区间的窗口

3. 具体实现

#include <bits/stdc++.h>
using namespace std;

const int N = 1e6 + 10;

struct Lawyer {
    int l, r, id;
    bool operator<(const Lawyer& other) const {
        return l < other.l;
    }
} lawyers[N];

int main() {
    int n, k;
    scanf("%d%d", &n, &k);
    
    for (int i = 0; i < n; i++) {
        scanf("%d%d", &lawyers[i].l, &lawyers[i].r);
        lawyers[i].id = i + 1;
    }
    
    // 按左端点排序
    sort(lawyers, lawyers + n);
    
    // 使用multiset维护右端点
    multiset<int> rights;
    int max_len = 0;
    int best_l = 0, best_r = 0;
    
    for (int i = 0; i < n; i++) {
        rights.insert(lawyers[i].r);
        
        // 如果当前区间数超过k，移除左端点最小的区间
        if (rights.size() > k) {
            rights.erase(rights.begin());
        }
        
        // 当有k个区间时，计算交集长度
        if (rights.size() == k) {
            int current_l = lawyers[i].l;
            int current_r = *rights.begin();  // 第k小的右端点
            
            if (current_r - current_l > max_len) {
                max_len = current_r - current_l;
                best_l = current_l;
                best_r = current_r;
            }
        }
    }
    
    printf("%d\n", max_len);
    
    // 输出选择的律师编号
    vector<int> selected;
    for (int i = 0; i < n && selected.size() < k; i++) {
        if (lawyers[i].l <= best_l && lawyers[i].r >= best_r) {
            selected.push_back(lawyers[i].id);
        }
    }
    
    for (int i = 0; i < k; i++) {
        printf("%d ", selected[i]);
    }
    printf("\n");
    
    return 0;
}

算法正确性证明

为什么这样能找到最优解？

1. 枚举所有可能的左端点：

   • 当我们按左端点排序后，对于每个位置 $i$，我们考虑以 $lawyers[i].l$ 作为交集的左端点
   • 这是因为交集的左端点一定是某个区间的左端点

2. 选择右端点：

   • 对于固定的左端点，我们需要选择右端点尽可能大的区间
   • 但为了最大化交集，我们需要选择第 $k$ 小的右端点（因为交集右端点由最小的右端点决定）
   • 使用multiset可以高效地维护当前窗口中第 $k$ 小的右端点

3. 滑动窗口的合理性：

   • 当右指针移动时，我们总是加入新的区间
   • 当区间数超过 $k$ 时，我们移除右端点最小的区间（因为它限制了交集的大小）

复杂度分析

• 排序：$O(n \log n)$
• 双指针扫描：$O(n \log k)$（每个区间插入/删除multiset一次）
• 总复杂度：$O(n \log n)$，对于 $n \leq 10^6$ 是可接受的

优化版本（使用堆）

#include <bits/stdc++.h>
using namespace std;

const int N = 1e6 + 10;

struct Lawyer {
    int l, r, id;
    bool operator<(const Lawyer& other) const {
        return l < other.l;
    }
} lawyers[N];

int main() {
    int n, k;
    scanf("%d%d", &n, &k);
    
    for (int i = 0; i < n; i++) {
        scanf("%d%d", &lawyers[i].l, &lawyers[i].r);
        lawyers[i].id = i + 1;
    }
    
    sort(lawyers, lawyers + n);
    
    // 使用最大堆维护最小的k个右端点
    priority_queue<int, vector<int>, greater<int>> pq;
    int max_len = 0;
    int best_l = 0;
    
    for (int i = 0; i < n; i++) {
        pq.push(lawyers[i].r);
        
        if (pq.size() > k) {
            pq.pop();
        }
        
        if (pq.size() == k) {
            int current_len = pq.top() - lawyers[i].l;
            if (current_len > max_len) {
                max_len = current_len;
                best_l = lawyers[i].l;
            }
        }
    }
    
    printf("%d\n", max_len);
    
    // 重构解
    vector<int> selected;
    for (int i = 0; i < n && selected.size() < k; i++) {
        if (lawyers[i].l <= best_l && lawyers[i].r >= best_l + max_len) {
            selected.push_back(lawyers[i].id);
        }
    }
    
    for (int i = 0; i < k; i++) {
        printf("%d ", selected[i]);
    }
    printf("\n");
    
    return 0;
}

样例解释

对于样例：

6 3
3 8
4 12  
2 6
1 10
5 9
11 12

算法过程：

1. 排序后：[1,10], [2,6], [3,8], [4,12], [5,9], [11,12]
2. 当处理到 [4,12] 时，堆中包含 [2,6], [3,8], [4,12] 的右端点：6,8,12
3. 第3小的右端点是8，交集为 [4,8]，长度4
4. 输出律师编号 1 2 4（对应原始输入顺序）

总结

这道题的关键在于：

1. 认识到最优解的交集端点一定是输入区间的端点
2. 使用排序 + 堆/平衡树来高效维护第k小的右端点
3. 通过双指针枚举所有可能的左端点