c*********t
发帖数: 2921 | 1 Given
抛物线：y = ax^2 + bx + c （a≠0)
给了一些y的值，这些y值(y_1, y_2,..., y_n)是在x=x_1, x_2, x_3, ....., x_n 对
应的y.
x_1
of x's are unknown.
问: 如何对y排序?
Thanks |
H*M
发帖数: 1268 | 2 先求出拐点(倒数为0），assume a>0
然后拐点左边的是倒着排序好的，右边是排序好的
再merge一下，不过得有点trick,一个从头，一个从尾。
value
【在 c*********t 的大作中提到】
: Given
: 抛物线：y = ax^2 + bx + c （a≠0)
: 给了一些y的值，这些y值(y_1, y_2,..., y_n)是在x=x_1, x_2, x_3, ....., x_n 对
: 应的y.
: x_1: of x's are unknown.
: 问: 如何对y排序?
: Thanks
|
c*********t
发帖数: 2921 | 3 How to find 拐点 efficiently? In O(n) or O(logn)?
Another thing is that we do now know whether a>0 or not in advance.
So wee need to determine the sign of a.
【在 H*M 的大作中提到】
: 先求出拐点(倒数为0），assume a>0
: 然后拐点左边的是倒着排序好的，右边是排序好的
: 再merge一下，不过得有点trick,一个从头，一个从尾。
:
: value
|
g*******y
发帖数: 1930 | 4 O(1)...
就是算抛物线的对称轴吧
【在 c*********t 的大作中提到】
: How to find 拐点 efficiently? In O(n) or O(logn)?
: Another thing is that we do now know whether a>0 or not in advance.
: So wee need to determine the sign of a.
|
H*M
发帖数: 1268 | 5 拐点不就是可以手算得吗
或者一个式子就行了
不知道a>0 <0也没关系
算出拐点之后,稍微多找两个点测下就知道了,因为左边和右边是分别单调的
【在 c*********t 的大作中提到】
: How to find 拐点 efficiently? In O(n) or O(logn)?
: Another thing is that we do now know whether a>0 or not in advance.
: So wee need to determine the sign of a.
|
k***e
发帖数: 556 | 6 怎么不告诉完全的答案呢 ：）
三点就可以确定二次曲线的方程
你有n个点 所以。。。
【在 g*******y 的大作中提到】
: O(1)...
: 就是算抛物线的对称轴吧
|
b***e
发帖数: 1419 | 7 我对你的景仰, 有如滔滔江水, 绵绵不绝.
【在 k***e 的大作中提到】
: 怎么不告诉完全的答案呢 ：）
: 三点就可以确定二次曲线的方程
: 你有n个点 所以。。。
|
b***e
发帖数: 1419 | 8 这个直接从两头merge不就行了吗. 你不是已经知道是变相的merge sort了吗?
value
【在 c*********t 的大作中提到】
: Given
: 抛物线：y = ax^2 + bx + c （a≠0)
: 给了一些y的值，这些y值(y_1, y_2,..., y_n)是在x=x_1, x_2, x_3, ....., x_n 对
: 应的y.
: x_1: of x's are unknown.
: 问: 如何对y排序?
: Thanks
|
k***e
发帖数: 556 | 9 为啥讽刺俺？ ：《
【在 b***e 的大作中提到】
: 我对你的景仰, 有如滔滔江水, 绵绵不绝.
|
l****h
发帖数: 272 | 10 这倒题目主要是要你知道Y值在抛物线的一边是递减，另一边是递增的。先找四点确定a
>0 or a<0.接着找到极值点。极值点将序列分成两段已经排序的子序列。在把两子序列
合并排序即可。
value
【在 c*********t 的大作中提到】
: Given
: 抛物线：y = ax^2 + bx + c （a≠0)
: 给了一些y的值，这些y值(y_1, y_2,..., y_n)是在x=x_1, x_2, x_3, ....., x_n 对
: 应的y.
: x_1: of x's are unknown.
: 问: 如何对y排序?
: Thanks
|
b***e
发帖数: 1419 | 11 为什么大家盯着极值点？ 知道a正负直接两头merge就成了。
定a
【在 l****h 的大作中提到】
: 这倒题目主要是要你知道Y值在抛物线的一边是递减，另一边是递增的。先找四点确定a
: >0 or a<0.接着找到极值点。极值点将序列分成两段已经排序的子序列。在把两子序列
: 合并排序即可。
:
: value
|
H*M
发帖数: 1268 | 12 yeah
but u still need to do a little bit checking to see if all the points is mon
o-inc or dec..small work
【在 b***e 的大作中提到】
: 为什么大家盯着极值点？ 知道a正负直接两头merge就成了。
:
: 定a
|
l****h
发帖数: 272 | 13 The extreme point will tell you when to stop merging.
【在 b***e 的大作中提到】
: 为什么大家盯着极值点？ 知道a正负直接两头merge就成了。
:
: 定a
|
b***e
发帖数: 1419 | 14 Just merge, and when reaching the extreme, you will naturally know and
stop. You do NOT have to waste a separate cycle to compute the extreme.
Get it?
【在 l****h 的大作中提到】
: The extreme point will tell you when to stop merging.
|
