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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 先求出拐点(倒数为0),assume a>0 : 然后拐点左边的是倒着排序好的,右边是排序好的 : 再merge一下,不过得有点trick,一个从头,一个从尾。 : : value
|
g*******y 发帖数: 1930 | 4 O(1)...
就是算抛物线的对称轴吧
【在 c*********t 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : O(1)... : 就是算抛物线的对称轴吧
|
b***e 发帖数: 1419 | 7 我对你的景仰, 有如滔滔江水, 绵绵不绝.
【在 k***e 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 怎么不告诉完全的答案呢 :) : 三点就可以确定二次曲线的方程 : 你有n个点 所以。。。
|
b***e 发帖数: 1419 | 8 这个直接从两头merge不就行了吗. 你不是已经知道是变相的merge sort了吗?
value
【在 c*********t 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 我对你的景仰, 有如滔滔江水, 绵绵不绝.
|
l****h 发帖数: 272 | 10 这倒题目主要是要你知道Y值在抛物线的一边是递减,另一边是递增的。先找四点确定a
>0 or a<0.接着找到极值点。极值点将序列分成两段已经排序的子序列。在把两子序列
合并排序即可。
value
【在 c*********t 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 这倒题目主要是要你知道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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 为什么大家盯着极值点? 知道a正负直接两头merge就成了。 : : 定a
|
l****h 发帖数: 272 | 13 The extreme point will tell you when to stop merging.
【在 b***e 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 为什么大家盯着极值点? 知道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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : The extreme point will tell you when to stop merging.
|