ihas1337一道题没看懂 - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>JobHunting - 待字闺中

ihas1337一道题没看懂

ihas1337一道题没看懂# JobHunting - 待字闺中

P*c2011-08-20 07:08

1 楼

http://www.ihas1337code.com/page/2
A Distance Maximizing problem
后面那个O(n)解法。找出valid的starting points之后，后面怎么又要shortest
starting point了呢。如果要shortest，至少也要把valid的starting points弄个排序
或者heap什么的吧。就不是O(n)了啊。

m*q2011-08-20 07:08

2 楼

这个题是要先扫描数组，维护一个递减子序列，就是start point的序列，
shortest start point是这个序列的最后一个元素。
然后从后面扫描，直到遇到一个元素大于递减子序列的最后一个元素，
计算差值，并把最后一个元素从递减子序列中去掉，然后比较递减
子序列的当前最后一个元素，然后继续扫描...
记得板上前一阵有过讨论

【在 P**********c 的大作中提到】

: http://www.ihas1337code.com/page/2
: A Distance Maximizing problem
: 后面那个O(n)解法。找出valid的starting points之后，后面怎么又要shortest
: starting point了呢。如果要shortest，至少也要把valid的starting points弄个排序
: 或者heap什么的吧。就不是O(n)了啊。

P*c2011-08-20 07:08

3 楼

怎么样O(n)维护一个递减子序列？

【在 m**q 的大作中提到】

: 这个题是要先扫描数组，维护一个递减子序列，就是start point的序列，
: shortest start point是这个序列的最后一个元素。
: 然后从后面扫描，直到遇到一个元素大于递减子序列的最后一个元素，
: 计算差值，并把最后一个元素从递减子序列中去掉，然后比较递减
: 子序列的当前最后一个元素，然后继续扫描...
: 记得板上前一阵有过讨论