这道题和其他用PQ来做解决“间隔约束”的任务规划问题很相似。但是本题的特点是,不需要输出具体的解决方案。为什么呢?因为本题给出的数据量很大,本质上会有1e5*1e9
个milestone需要安排。按照1054.Distant-Barcodes
的PQ做法,那么跑1e14/2
次PQ的弹出、加入操作,显然会TLE。
其实本题有明显的贪心算法。我们可以想象,如果某个任务X的milestone特别多,超过了总体的半数(加1),那么根据抽屉原理,必然有两个相同的任务X会相邻。反之,我们必然可以让任务X彼此之间至少间隔一位,让其他任务填充其中,也就是能完成所有milestone的安排。
对于前者,我们能安排的最多milestone数目的方案类似于XOXOXOXOXOX XXXX....
,显然答案的长度取决于非X的任务的milestone有多少个。