P**********c
发帖数: 3417 | 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**q
发帖数: 189 | 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**********c
发帖数: 3417 | 3 怎么样O(n)维护一个递减子序列？
【在 m**q 的大作中提到】
: 这个题是要先扫描数组，维护一个递减子序列，就是start point的序列，
: shortest start point是这个序列的最后一个元素。
: 然后从后面扫描，直到遇到一个元素大于递减子序列的最后一个元素，
: 计算差值，并把最后一个元素从递减子序列中去掉，然后比较递减
: 子序列的当前最后一个元素，然后继续扫描...
: 记得板上前一阵有过讨论
|
h**6
发帖数: 4160 | |
m**q
发帖数: 189 | 5 不用啊，就是一个stack，把数组第一个元素push进栈，
然后扫描数组，小于stack top的就push进栈，复杂度O(n)
【在 h**6 的大作中提到】
: 维护递减子序列似乎需要O(nlogn)
|
h**6
发帖数: 4160 | |
