algorithm - UVa 11860：如何使用堆来解决它

Question

我正在尝试解决UVa在线判断中的编程问题：

Uva 11860 文档分析仪

这个问题的问题设置者写了一个教程heap和一些操作，包括插入，删除节点，并在文章末尾提到 - 这个问题可以通过使用堆来解决。可能有其他方法可以解决它但我无法弄清楚如何设计这个问题来解决使用heap. 我知道如何在 C++ 中编写堆代码，并且可以定义insert()、remove()、print()函数和一些其他操作，例如查找最小项等。

这个问题与堆有什么关系？

Answer 1

想到的方法：

有一个（最初是空的）包含一个单词及其位置的对象堆 - 按位置对该堆进行排序。

smallestDistance = infinity
biggestSize = 0
for each word in the input:
   heap.insert(Pair(current position, word))
   hashMap[word] = current position

   // We saw the word after this occurrence, so remove it
   while hashMap[heap.minimum.word] != heap.minimum.position
     heap.pop()

   // We found another word!
   //   The previous smallest is invalid, since it doesn't contain this word
   if heap.size > biggestSize
     smallestDistance = currentPosition - heap.minimum
     biggestSize = heap.size
   // Is this distance better than the best so far? If so, use it instead
   else
     smallestDistance = min(smallestDistance, currentPosition - heap.minimum)
output smallestDistance