选玩具

选玩具

测试数据来自 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
通过率
?
上传者