#P1401. 2023.07.05-实习生笔试-第一题-小红养花
2023.07.05-实习生笔试-第一题-小红养花
Related
In following contests:
分别计算每种花所需要的水量,第i种花需要的水量为w[i]×(n−i)
然后对花按照所需要的水量从小到大进行排序,优先浇需要水量少的花
O(nlogn)
小红在闲暇时间喜欢养花。某次小红去一个城市出差 n 天,他带了一些花的种子,如果他种下了,那么那种花就会在特定的时间开放。
现在已知第i种花会在第i天开放,并且开放之后每天都要用 ai 的水。
举个例子,当 n=3,a=[1,2,3] 时,如果小红种下了第二种花的种子,那么他就要在第二天、第三天和第四天各浇灌 2 升水,总共是 6 升水。
但是由于小红出差经费有限,小红可以用到养花上的水量为 m 升。现在小红想知道,如果他可以放弃一部分种子,最多能种多少种花呢?
输入第一行两个正整数 n 和 m 。(1≤n≤100,1≤m≤106)
输入第二行是 n 个正整数 ai (1≤ai≤104)表示每种花开放后每天的耗水量。
输出一个整数 ans 表示小红最多可种的花的种数。
样例输入
5 20
4 6 2 3 5
输出
3
说明
小红可以种下第三种第四种第五种花,之后第三天用水2升,第四天用水5升,第五天用水10升,总用水量 2+5+10=17 升。
输入
5 100
5 4 3 2 1
输出
5
In following contests: