题解：P14595 [COCI 2025/2026 #2] 集训 / Dodatna

Ray2009_ · 2025-11-24 18:33:05 · 题解

题目大意

给定 n 个学生在校的时间段 [l_i, r_i)，要求选择一段连续的上课时间 [start, end) 使得至少有 k 个学生在这段时间内全程在校，求最长的上课时间长度。

思路

我们需要找到最大的 end - start 使得存在至少 k 个学生的在校区间完全包含在一段连续的上课时间中。

如果按照左端点对学生排序，那么对于每个候选的 start（取某个学生的 l_i），我们只需要考虑左端点 \leq start 的学生，并从中选择右端点最大的 k 个学生。这些学生中最小右端点决定了 end 的最大值。

步骤

按左端点排序，用最小堆维护右端点，当堆大小达到k时，用堆顶最小右端点计算区间长度并更新最大值。

赛时代码

#include<bits/stdc++.h>
using namespace std;
pair<int,int>a[300078];
int main(){
    int n,k;
    cin>>n>>k;
    for(int i=1;i<=n;i++) cin>>a[i].first>>a[i].second;
    sort(a+1,a+n+1);
    priority_queue<int,vector<int>,greater<int>> pq;
    long long ans=0;
    for(int i=1;i<=n;i++){
        pq.push(a[i].second);
        if(pq.size()>k) pq.pop();
        if(pq.size()==k){
            int ed=pq.top();
            if(ed>a[i].first) ans=max(ans,(long long)ed-a[i].first);
        }
    }
    cout<<ans;
    return 0;
}//按左端点排序，用最小堆维护右端点，当堆大小达到k时，用堆顶最小右端点计算区间长度并更新最大值。