题解：P5754 [JSOI2010] 排名

_WHX985_ · 2025-01-14 11:42:40 · 题解

前言

这道题分为两个问，想要过这道题需要先了解一个算法 STL。不会的谷友们建议去学一下，这对你以后的编程生涯会非常有用。

STL 学习链接

正文

前言已经说了，这题分为两个问，我们可以分开讨论。 先来看第一个问，第一个问可以直接使用 STL 中的优先队列和拓扑排序，优先队列就相当于一个堆，分为大根堆和小根堆，大根堆指父亲节点一定比孩子节点大，而小根堆指父亲节点一定比孩子节点小。下面左图为大根堆，右图为小根堆。 对于第二个问，和第一个问很像，只需用大根堆维护拓扑排序即可。