如果我们将三种元素组成一个序列,一次取俩,每次抓取尽量要是不同的元素。言下之意就是希望将不同元素尽量间隔分布。于是这道题的本质就是767.Reorganize-String
。
基本思想是,每个回合尽量使用当前剩余频次最多的两种元素,这样就能尽量最大化剩下元素的种类数,方便尽可能持久地凑成pair。所以我们用一个大顶堆的pq,每次读取最大的两个元素,各自减一后再放回去,直至pq里面只剩下一种元素。
假设元素的总个数是total,如果最多元素的种类占据了二分之一以上,即amount[0]>=total/2+1
,那么我们就无法保证间隔排列,所以必须操作amount[0]次,每次要么搭配一个其他种类的元素,要么自己单独被取出。反之,如果amount[0]<total/2+1
,那么就可以保证间隔排列,每次都可以取出一对(除非最后一轮落单),所以需要的操作总次数就是(total+1)/2