本题有更优做法
查看原帖
本题有更优做法
558743
isitover楼主2023/7/13 20:36

题解区都是 O(nlog⁡n)O(n \log n) 算法,但显然有一个更优的 O(n)O(n) 算法,发不了题解了,在这里简要写一下:

考虑以下算法:

注意到若某个非 ii 的人 jj 满足 sj∈[si,ti]s_j \in[s_i,t_i],则 jj 会向 ii 问好。

应此只要求出关于前 ii 秒到达人数的前缀和 aia_i, 则答案便是 ati−asi−1−1a_{t_i}-a_{s_i-1}-1。

代码长度也远低于题解,不卡常轻松最优解。

2023/7/13 20:36
加载中...