1 solutions
-
1
我们将一个人的成绩对应到二维空间中的位置向量,,一种排名的计算步骤被抽象为
- 确定一个法向量, 这个法向量需要满足这些条件:
- 指向第一象限()
- $\text{GPA}_i=v[0]p[0]+v[1]p[1]=\vec v \cdot \vec p_i$,随后就可以得到小林排名。
为什么这里不需要限制呢?这是因为只要,计算出来的GPA只是等比例放大缩小,不影响排名。
设小林的位置向量是,利用当作方向向量的法向量(notice that!),可以确定一个过点的直线(关于的函数)。
虽然千变万化,但是我们并不需要考虑那么多的情况,实际上我们只需要考虑:
- 经过包括点的至少两个点
设表示如果确定直线是,小林的排名是多少,我们发现使得小林排名最高的中,一定至少有一个经过了包括点的至少两个点,即"临界条件"(使得变化)。
而还有两个临界条件,分别就是。
此时算法就有了,枚举一个点,法向量就是找到个(或者),然后计算所有人的GPA得到小林的排名。记得把这几种情况考虑进去。
其实有个做法,在这个基础上优化一下而已。你注意到,在点右上和左下的点不需要管(Q对他们有绝对劣势或者绝对优势),只需要考虑左上和右下的点。而左上和右下的点对答案的贡献是关于直线的斜率的分段函数和,分别把和计算出来之后,再枚举斜率,利用双指针找到和统计答案即可。
Information
- ID
- 159
- Time
- 1000ms
- Memory
- 256MiB
- Difficulty
- 10
- Tags
- (None)
- # Submissions
- 650
- Accepted
- 18
- Uploaded By