Problem 3476 --小刘学长的福利

3476: 小刘学长的福利

"
Time Limit $1$ 秒/Second(s) Memory Limit $512$ 兆字节/Megabyte(s)
提交总数 $1$ 正确数量 $1$
裁判形式 标准裁判/Standard Judge 我的状态 尚未尝试
难度 分类标签 高精度

又是一年ACM集训的时刻,小刘学长邀请n位同学来玩一个有奖游戏。首先,他让每个同学在左、右手上面分别写下一个整数,小刘学长自己也在左、右手上各写一个整数。然后,让这n位同学排成一排,小刘学长站在队伍的最前面。排好队后,所有的同学都会获得小刘学长分发的若干肉松饼,每位同学获得的肉松饼数分别是:排在该同学前面的所有人的左手上的数的乘积除以他自己右手上的数,然后向下取整得到的结果。 

小刘学长不希望某一个同学获得特别多的福利,所以他想请你帮他重新安排一下队伍的顺序,使得获得福利最多的同学,所获福利尽可能的少。注意,小刘学长的位置始终在队伍的最前面。 

【数据范围】 对于100%的数据,有 n 1,0000 < ab < 10000

第一行一个n表示n个同学
第二行两个数字代表小刘学长左手和右手的数字
接下来的n行分别代表第n个同学左手和右手的数字
一个数字代表获得福利最多同学所获得福利
3
1 1
2 3
7 4
4 6
2
按1、2、3号同学这样排列队伍,获得福利最多的同学所获得肉松饼数为2; 
按1、3、2这样排列队伍,获得福利最多的同学所获得肉松饼数为2;
按2、1、3这样排列队伍,获得福利最多的同学所获得肉松饼数为2;
按2、3、1这样排列队伍,获得福利最多的同学所获得肉松饼数为9;
按3、1、2这样排列队伍,获得福利最多的同学所获得肉松饼数为2;
按3、2、1这样排列队伍,获得福利最多的同学所获得肉松饼数为9。
因此,福利最多的同学最少获得2个肉松饼,答案输出2。

推荐代码 查看3476 所有题解 上传题解视频得图灵币

本题记录 用 户(点击查看用户) 运行号(点击购买题解) 时 间
算法最快[$0 $ms] aoj_judger 615301 2020-10-08 13:49:54
内存最少[$2044 $KB] aoj_judger 615301 2020-10-08 13:49:54
第一AC aoj_judger 615301 2020-10-08 13:49:54
第一挑战 aoj_judger 615301 2020-10-08 13:49:54

赛题来源/所属竞赛 N/A

竞赛编号 竞赛名称 竞赛时间 访问比赛