题意

给定 $n$ 个闹钟，每个闹钟在若干时刻响起。要从中恰好选出 $k$ 个闹钟，使得存在 $(l,r)$ 没有任何被选中的闹钟响起。求最大可能的区间长度。

思路

发现 $(l,r)$ 区间内恰好 $k$ 个闹钟不响，实际上等价于 $n-k$ 个闹钟响。

因此二分答案 $x$，检查是否存在长度为 $x$ 的开区间，其内部不同闹钟数 $\le n-k$。

很明显，首先对每一个闹钟响的时间进行排序。

那么可以用双指针维护当前区间有多少闹钟响，如果以 $l$ 为左端点的最长区间的时间差 $\ge x$，说明可行。

要把两边的时间点 $0$ 和 $T$ 加入。

代码

#include <bits/stdc++.h>
using namespace std;
const int N=3e5+5;
int n,k,T,tot,cnt[N];
struct node{int tim,type;}a[N];
bool cmp(node x,node y){return x.tim<y.tim;}

bool check(int x){
    memset(cnt,0,sizeof cnt);
    int d=0,l=1;
    for(int i=2;i<=tot;i++){
        if(i-1>l&&a[i-1].type)d+=(++cnt[a[i-1].type]==1);
        while(d>n-k){
            if(l+1<i&&a[l+1].type)d-=(--cnt[a[l+1].type]==0);
            l++;
        }
        if(a[i].tim-a[l].tim>=x)return 1;
    }
    return 0;
}

int main(){
    ios::sync_with_stdio(0);cin.tie(0);
    cin>>n>>k>>T;
    a[++tot]={0,0};
    for(int i=1,m;i<=n;i++){
        cin>>m;
        while(m--){int t;cin>>t;a[++tot]={t,i};}
    }
    sort(a+1,a+tot+1,cmp);
    a[++tot]={T,0};
    int l=0,r=T,ans,mid;
    while(l<=r)check(mid=l+r>>1)?ans=mid,l=mid+1:r=mid-1;
    cout<<ans;
}