Skip to content

1461: 小V买平安果

题目

题目描述

圣诞节刚过去,小V感到很酸

因为在平安夜、圣诞节两天,小V连续肝了32个小时赶ddl,然而pyq圈里全是一片过节的氛围

为了缓解这一感受,小V打算去补买平安果

小V去超市买平安果,他发现货架上有N个平安果,每个平安果都有一个重量$W_i$和价格$C_i$.

小V身上只带了S元钱,因此他想要买一个价格不超过S的平安过回家,

另外,他希望他买的那个苹果的性价比尽量高。

性价比的定义是重量除以价格,即第i个苹果的性价比是$W_i$/$C_i$.

你的任务是告诉小V,他应该买第几个苹果。

输入格式

输入文件第一行包含两个正整数N,S

输入文件第2~N+1行,每行包含两个正整数$W_i$,$C_i$,第i+1行的数表示第i个平安过的重量和价格。

输出格式

输出文件第一行仅包含一个数K,

表示购买第K只平安果能使小V在可以接受的价格内获得最高的性价比。题目保证答案唯一

样例输入

4 15

4 8

4 10

8 10

10000 20

样例输出

3

数据范围

对于100%的数据,满足0<N<=100000;0<S<=10^9;

0<$W_i$,$C_i$<=10^9; N,S,$W_i$,$C_i$均为整数

Oops! 本题目还没有解答!

助教老师们编题的速度,已经超过了解题的速度!

OJ翻了一新,但本解答集还大多用的是2017-2019级,甚至更早的同学们贡献的答案。

如果你已经AC了,可以的话,请您参考添加页面,与大家一起分享你的题解!