「KTSC 2023 R2」学生 题解

问题分析

这是一个关于分布式知识推理的经典问题。N名学生组成M个辅导小组，每个小组排除区间[L,R]内的学生。学生只能基于自己所在的组和投诉情况逐步推理，目标是确定投诉发生的天数和投诉的学生。

---

核心思路

关键观察

1. 投诉天数 = 覆盖所有排除区间的最大不相交区间数
2. 学生i在第k天投诉 ⇔ 覆盖i左右两边区间需要k-1天，且总覆盖需要k天

算法框架

1. 计算覆盖所有区间的最大不相交区间数K
2. 对每个学生i，计算覆盖i左边和右边区间的最大不相交区间数
3. 如果左边覆盖数 + 右边覆盖数 + 1 = K，则学生i在第K天投诉

---

代码实现详解

数据结构与初始化

std::pair<int, std::vector<int>> complaint(int N, std::vector<int> L, std::vector<int> R) {
    int M = L.size();
    std::vector<std::tuple<int, int>> seg;
    seg.reserve(M);
    
    // 将每个辅导小组存储为区间
    for (int i = 0; i < M; i++) {
        seg.emplace_back(L[i], R[i]);
    }

区间排序处理

// 复制两份区间，用于不同方向的处理
std::vector<std::tuple<int, int>> _seg(seg);

// 按右端点升序排序 - 用于从左到右的覆盖计算
std::sort(seg.begin(), seg.end(), [](const auto &x, const auto &y) {
    return std::get<1>(x) < std::get<1>(y);
});

// 按左端点降序排序 - 用于从右到左的覆盖计算
std::sort(_seg.begin(), _seg.end(), [](const auto &x, const auto &y) {
    return std::get<0>(x) > std::get<0>(y);
});

计算最大不相交区间数

std::vector<int> cnt(M + 1), _cnt(M + 1);

// 从左到右计算最大不相交区间数
for (int i = 0, last_right = -1; i < M; i++) {
    cnt[i + 1] = cnt[i];  // 前缀和
    
    // 如果当前区间与已选区间不相交，选择它
    if (last_right < std::get<0>(seg[i])) {
        cnt[i + 1]++;
        last_right = std::get<1>(seg[i]);
    }
}

// 从右到左计算最大不相交区间数
for (int i = 0, last_left = N; i < M; i++) {
    _cnt[i + 1] = _cnt[i];
    
    // 如果当前区间与已选区间不相交，选择它
    if (last_left > std::get<1>(_seg[i])) {
        _cnt[i + 1]++;
        last_left = std::get<0>(_seg[i]);
    }
}

算法说明：

• cnt[i]：前i个区间（按右端点排序）中的最大不相交区间数
• _cnt[i]：前i个区间（按左端点降序排序）中的最大不相交区间数

确定投诉学生

std::vector<int> ans;
int ptr_right = 0, ptr_left = M;

for (int student = 0; student < N; student++) {
    // 移动指针：找到右端点 < student 的最后一个区间
    while (ptr_right < M && std::get<1>(seg[ptr_right]) < student) {
        ptr_right++;
    }
    
    // 移动指针：找到左端点 > student 的最后一个区间  
    while (ptr_left > 0 && std::get<0>(_seg[ptr_left - 1]) <= student) {
        ptr_left--;
    }
    
    // 关键判断条件
    if (cnt[ptr_right] + _cnt[ptr_left] + 1 == cnt[M]) {
        ans.push_back(student);
    }
}

判断条件解释：

• cnt[ptr_right]：完全在student左边的区间中的最大不相交区间数
• _cnt[ptr_left]：完全在student右边的区间中的最大不相交区间数
• cnt[M]：所有区间中的最大不相交区间数（总投诉天数）

学生student在第cnt[M]天投诉的条件是：覆盖其左右两边需要cnt[M]-1天，第cnt[M]天才轮到自己被发现。

---

算法正确性证明

为什么最大不相交区间数等于投诉天数？

考虑推理过程：

• 第1天：被所有区间排除的学生立即投诉
• 第2天：学生通过第1天没有投诉，推断出存在不包含自己但包含其他人的区间
• 第k天：需要前k-1天的信息才能推断出自己被排除

最大不相交区间数恰好对应这个渐进式的推理过程。

学生投诉时间判断的正确性

对于学生i：

• 需要cnt[ptr_right]天发现左边被排除的学生
• 需要_cnt[ptr_left]天发现右边被排除的学生
• 第cnt[ptr_right] + _cnt[ptr_left] + 1天才能推断出自己被排除
• 当这个值等于总天数时，学生i在最后一天投诉

---

复杂度分析

时间复杂度

• 排序：$O(M \log M)$
• 前缀计算：$O(M)$
• 学生判断：$O(N + M)$（双指针）
• 总复杂度：$O((N + M) \log M)$

空间复杂度

• 区间存储：$O(M)$
• 前缀数组：$O(M)$
• 结果数组：$O(N)$
• 总空间：$O(N + M)$

---

样例验证

样例1

N=6, 区间: [1,4], [2,5], [3,3]
最大不相交区间数: 1
第1天投诉: 学生3

样例2

N=10, 区间: [1,4], [4,7], [8,9], [2,6]
最大不相交区间数: 2  
第2天投诉: 学生4,8,9

样例3

N=5, 区间: [0,4]
最大不相交区间数: 1
第1天投诉: 所有学生

---

总结

本题的解法展现了几个重要技巧：

$1.$ 问题转化：将分布式推理转化为区间覆盖问题

$2.$ 贪心选择：使用经典算法计算最大不相交区间数

$3.$ 前缀优化：通过预处理避免重复计算

$4.$ 双指针：高效确定每个学生的相关区间范围

算法在时间和空间复杂度上都达到最优，能够处理$N, M \leq 2.5 \times 10^5$的大规模数据，是该问题的标准解法。