Skip to content

Latest commit

 

History

History
 
 

1057.Campus-Bikes

Folders and files

NameName
Last commit message
Last commit date

parent directory

..
 
 
 
 

1057.Campus-Bikes

此题考查如何设计数据结构来方便解题。

设计数组d,其中每个d[i]是一个队列,盛装第i个工人到每辆自行车的距离信息{dist, i, j},并且是已经排序的。

我们每个回合解决一个工人。在每个回合中,将所有d[i]的首元素(见上,是一个三元triplet)放入一个新的优先队列(或者有序集合),这样集合里的第一个元素自然就是一个当前成功的配对(因为优先队列按照距离、工人编号、自行车编号依次排序)。再下一个回合时,我们会跳过所有已经匹配过的工人,同时对于未匹配的工人i,如果d[i]的首元素是已经匹配过的自行车,我们也将其从d[i]弹出,直至首元素遇到的是未匹配的自行车,再将该tripet放入优先队列中。