「[NordicOI 2026] Alarms」题解

这个题可以用二分答案，离散化和滑动窗口。

题目要求在给定的时间区间内，找到最长的连续子区间，使得区间内响起的不同闹钟数量不超过，也就是允许至少个闹钟全程静音。主要问题在于如何处理大量离散的闹钟时间点，并判断任意区间内的闹钟覆盖情况。

离散化：提取所有闹钟时间和还有后排序去重，将连续时间转化为离散的关键点。这样就能将问题转化成在离散点之间寻找最长合法区间。
将每个闹钟时间对应到对应的离散时间点，记录每个时间点有哪些闹钟响起。
滑动窗口：用双指针维护一个滑动窗口，动态统计窗口内不同闹钟的数量。如果当前数量超过限制，移动左指针缩小窗口，否则右移右指针，并更新最长合法区间长度。

AC Code

#include <bits/stdc++.h>
#define int long long
#define rest(i,n,m) for(int i=n;i<m;i++)
using namespace std;
const int MXN=3e5+7;
const int MXM=3e5+7;
const int MXT=3e5+17; 
int ut[MXT]; 
int uc=0;
struct edge{int t,id;}a[MXM],e[MXM];
int sum=0;
int eid[MXT],ec[MXT];    
int cnt[MXN],t[MXM+2],f[MXT];;
int N,K,T;
bool cmp(edge a,edge b){return a.t<b.t;}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>N>>K>>T;
    rest(i,0,N) {
        int m;
        cin>>m;
        rest(j,0,m) {
            int t;
            cin>>t;
            a[sum].t=t;
            a[sum].id=i;
            sum++;
        }
    }
    int tct=0;
    t[tct++]=0;
    t[tct++]=T;
    rest(k,0,sum) t[tct++]=a[k].t;
    sort(t,t+tct);
    uc=0;
    rest(i,0,tct) 
        if (i==0 or t[i]!=t[i-1]) 
			ut[uc++]=t[i];
    sort(a,a+sum, cmp);
    rest(k,0,sum) {
        int idx=lower_bound(ut,ut+uc,a[k].t)-ut;
        ec[idx]++;
    }
    eid[0]=0;
    rest(i,1,uc) eid[i]=eid[i-1]+ec[i-1];
    rest(i,0,uc) f[i]=eid[i];
    rest(k,0,sum) {
        int idx=lower_bound(ut,ut+uc,a[k].t)-ut;
        int pos=f[idx]++;
        e[pos]=a[k];
    }
    int mx=N-K;
    memset(cnt,0,sizeof cnt);
    int s=0;
    int ans=0;
    int l=0; 
    rest(r,0,uc) {
        if (r-1>l) {
            int ix=r-1;
            int res=eid[ix];
            int end=res+ec[ix];
            rest(p,res,end) {
                int id=e[p].id;
                if (cnt[id]==0) s++;
                cnt[id]++;
            }
        }
        while(s>mx){
            if(l+1<r){
                int ix=l+1;
                int res=eid[ix];
                int end=res+ec[ix];
                rest(p,res,end){
                    int id=e[p].id;
                    cnt[id]--;
                    if(cnt[id]==0) s--;
                }
            }
            l++;
        }
        if(r>l) ans=max(ans,ut[r]-ut[l]);
    }
    cout<<ans<<endl;
    exit(0);
}

AC Code

暂无评论