水原_

题解 P1080 国王游戏

题解

ACM(13)

/ 注册

P1080 国王游戏

513 浏览 0 回复 2020-01-02

水原_

+关注

国王游戏 - 洛谷

https://www.luogu.com.cn/problem/P1080

对于本题而言,记 $s$ 为 $i,j$ 前面的人的左手乘积,

$i,j$ 比 $j,i$ 优等价于:

$max(s/b[i],s*a[i]/b[j])<max(s/b[j],s*a[j]/b[i])$

等价于 $max(b[j],a[i]*b[i])<max(b[i],a[j]*b[j])$

可以推出 $a[i]*b[i]<a[j]*b[j].$

故按照 $a[i]*b[i]$ 排序即可.

举报

收藏

赞

评论加载中...