【NOIP2015】跳石头

也是一道坑害无数人的题啊。

一般来说看到这道题第一思路应该是堆+贪心,复杂度O(nlogn)好像是对的……然而这样做并不对……可以构造出很多反例。

正确的做法应该是二分答案+贪心,每次二分出一个答案k,从第二块石头到最后一块石头扫一遍,如果当前石头离上一块没有被去掉的石头距离小于k则说明当前石头需要被去掉。如果去掉的石头数大于限定的m则二分小的那边,反之二分大于等于的那边。

那么为什么这里的贪心又可以了呢?

堆+贪心中,在两个石头之间距离最小时,你不能判断到底去掉哪一个。因为你不知道去掉会对最后有什么影响。但这里的贪心不存在这样的问题。因为你是按顺序扫描的,如果当前石头与前面一个石头的距离小于k,则你肯定要去掉当前石头而不会去掉前面的石头,因为后一块石头到当前石头的距离肯定小于到上一块石头的距离(仔细想想就懂了)。时间复杂度O(nlogL)。

说点什么

  Subscribe  
提醒