HDU 6557 – Justice

题目链接:CCPC 2018 吉林赛区 C题

两个$x$可以合并得到$x-1$。使用大根堆维护当前未合并的所有数字,每次取两个出来,看是否相等,如果相等就合并,不等就扔到大的,把小的在放进堆。在合并的时候用并查集维护谁和谁合并到一起,当优先队列中出现了第一个1的时候,更新分组。

渐进时间复杂度$O(n \log n)$。

 

说点什么

avatar
50
  Subscribe  
提醒