选玩具
测试数据来自 wjszez/1929
【问题描述】
小明想要一些玩具。它决定从 N (3 <= N <= 25,000)种不同的玩具中选三个玩具。
第i个玩具有两个值美观值J_i (0 <= J_i <= 1,000,000) 和价格P_i (0 < P_i <=
100,000,000)。小明的钱足够买其中任意三个玩具。
小明希望要买的三个玩具的J_i/P_i值相加之和最大。这个值保证是唯一的。
例如有6个玩具:
i J_i P_i J_i/P_i
- --- ----- -------------------
1 0 521 0.00000
2 442 210 2.10476...
3 119 100 1.19000
4 120 108 1.11111...
5 619 744 0.83198...
6 48 10 4.80000
小明将买第6个、第2个和第3个玩具。
输入格式:
第一行:一个整数N
第2..N+1行:第i+1行两个整数J_i和P_i
输入样例(toyshop.in):
6
0 521
442 210
119 100
120 108
619 744
48 10
输出格式:
第一行: 小明得到的三个玩具的P_i值之和
第2..4行: 降序输出选中的三个玩具编号,每个编号一行
输出样例(toyshop.out):
320
6
2
3
信息
- ID
- 2339
- 难度
- (无)
- 分类
- (无)
- 标签
- 递交数
- 0
- 已通过
- 0
- 通过率
- ?
- 上传者