Skip to content

Latest commit

 

History

History
 
 

1953.Maximum-Number-of-Weeks-for-Which-You-Can-Work

Folders and files

NameName
Last commit message
Last commit date

parent directory

..
 
 
 
 

1953.Maximum-Number-of-Weeks-for-Which-You-Can-Work

这道题和其他用PQ来做解决“间隔约束”的任务规划问题很相似。但是本题的特点是,不需要输出具体的解决方案。为什么呢?因为本题给出的数据量很大,本质上会有1e5*1e9个milestone需要安排。按照1054.Distant-Barcodes的PQ做法,那么跑1e14/2次PQ的弹出、加入操作,显然会TLE。

其实本题有明显的贪心算法。我们可以想象,如果某个任务X的milestone特别多,超过了总体的半数(加1),那么根据抽屉原理,必然有两个相同的任务X会相邻。反之,我们必然可以让任务X彼此之间至少间隔一位,让其他任务填充其中,也就是能完成所有milestone的安排。

对于前者,我们能安排的最多milestone数目的方案类似于XOXOXOXOXOX XXXX....,显然答案的长度取决于非X的任务的milestone有多少个。