1 solutions

  • 1
    @ 2022-9-11 22:16:36

    我们将一个人的成绩对应到二维空间中的位置向量,pi=(x,y)\vec p_i=(x,y),一种排名的计算步骤被抽象为

    1. 确定一个法向量v\vec v , 这个法向量需要满足这些条件:
    • vv>0\vec v \cdot \vec v > 0
    • v\vec v指向第一象限(v[0],v[1]0\vec v[0],\vec v[1]\ge 0)
    1. $\text{GPA}_i=v[0]p[0]+v[1]p[1]=\vec v \cdot \vec p_i$,随后就可以得到小林排名。

    为什么这里不需要限制v[0]+v[1]=1v[0]+v[1] = 1呢?这是因为只要v[0]+v[1]>0v[0]+v[1] > 0,计算出来的GPA只是等比例放大缩小,不影响排名。

    设小林的位置向量是Q\vec Q,利用v\vec v当作方向向量的法向量(notice that!),可以确定一个过Q\vec Q点的直线L(v)\mathbb L(\vec v)(关于v\vec v的函数)。

    虽然L(v)\mathbb L(\vec v)千变万化,但是我们并不需要考虑那么多的情况,实际上我们只需要考虑:

    • L(v)\mathbb L(\vec v)经过包括QQ点的至少两个点
    • v=x or y\vec v=x \text{ or } y

    rank(L)\text{rank}(\mathbb L)表示如果确定直线是L\mathbb L,小林的排名是多少,我们发现使得小林排名最高的L\mathbb L中,一定至少有一个L0\mathbb L_0经过了包括QQ点的至少两个点,即"临界条件"(使得rank(L)\text{rank}(\mathbb L)变化)。

    而还有两个临界条件,分别就是x,yx,y

    此时O(n2)O(n^2)算法就有了,枚举一个点RR,法向量就是找到个n, s.t. nRQ\vec n ,\text{ s.t. }\vec n\perp \vec {RQ} (或者n-\vec n),然后计算所有人的GPA得到小林的排名。记得把v=(1,0),(0,1)\vec v=(1,0),(0,1)这几种情况考虑进去。

    其实有个O(n)O(n)做法,在这个基础上优化一下而已。你注意到,在QQ点右上和左下的点不需要管(Q对他们有绝对劣势或者绝对优势),只需要考虑左上和右下的点。而左上和右下的点对答案的贡献是关于直线的斜率kk的分段函数ffhh,分别把ffgg计算出来之后,再O(n)O(n)枚举斜率,利用双指针找到f(p)f(p)g(q)g(q)统计答案即可。

    Information

    ID
    159
    Time
    1000ms
    Memory
    256MiB
    Difficulty
    10
    Tags
    (None)
    # Submissions
    650
    Accepted
    18
    Uploaded By