专栏文章

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

RRay2009_
P14595题解参与者 2已保存评论 1

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
1 条
当前快照
1 份
快照标识符
@min1gsh2
此快照首次捕获于
2025/12/01 19:01
3 个月前
此快照最后确认于
2025/12/01 19:01
3 个月前
查看原文

题目大意

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

思路

我们需要找到最大的 end−startend - start 使得存在至少 kk 个学生的在校区间完全包含在一段连续的上课时间中。
如果按照左端点对学生排序，那么对于每个候选的 startstart（取某个学生的 lil_i），我们只需要考虑左端点 ≤start\leq start 的学生，并从中选择右端点最大的 kk 个学生。这些学生中最小右端点决定了 endend 的最大值。

步骤

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

赛时代码

CPP
#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时，用堆顶最小右端点计算区间长度并更新最大值。

评论

共 1 条评论，欢迎与作者交流。

正在加载评论...