「致曾经的入门」ACM算法课三(经典数据结构与基础算法二)

usercorn源码分析中……

Posted by 许大仙 on July 31, 2017

一、排序

例题:Holiday Hotel 选择称心的旅馆(离海边距离尽量近,价格低越好)。D表示距离,C表示价格。输出称心的旅馆数目

input: 5 300 200 100 300 400 200 200 400 100 500 0

解题思路示意图

对数据进行排序,C,D都小的肯定在第一个(这家肯定称心),以此作为标准。再判断下一个相对C,D小的,看看是否在第一个的右上角。不在的话,则以这个作为判断第三个旅馆的标准。在的话那么这个旅馆不是称心旅馆,继续以第一个旅馆为标准,判断第三个旅馆是否称心。

代码二:类似于哈希排序,不停取最低的价格记录下来