题目内容

英雄联盟中新推出了 $n$ 名英雄，用长度为 $n$ 的数组 $costs$ 表示每位英雄的点券定价，其中 $costs[i]$ 是第 $i$ 名英雄的价格。你一共有 $coins$ 点券可以用于消费，希望买到尽可能多的英雄。每位英雄最多购买一次，并且选出的英雄必须按 $costs$ 给出的从左到右顺序依次获取（输出时保持这一相对顺序）。

若存在多种方案能买到相同数量的英雄，则选择总花费更少的方案；若总花费仍然相同，则优先购买下标更小的英雄。

给定价格数组 $costs$ 和点券数量 $coins$，请计算并返回能够买到的英雄价格列表。

请在 Solution 中实现：

• Python：buyMaxHeroes(self, costs, coins) -> List[int]
• Java：int[] buyMaxHeroes(int[] costs, int coins)
• C++：vector<int> buyMaxHeroes(vector<int>& costs, int coins)

输入描述

输入共一行，依次给出数组 $costs$ 与整数 $coins$，格式如下：

[costs_0,costs_1,...,costs_{n-1}],coins

输出描述

输出共一行，为按原顺序排列的已购英雄价格列表：

[p_0,p_1,...,p_{k-1}]

若无法购买任何英雄，输出 []。

数据范围

• $1 \le n \le 10^5$
• $1 \le costs[i] \le 10^4$
• $0 \le coins \le 10^9$

样例1

输入

[6,1,4,3,2],10

输出

[1,4,3,2]

说明

$costs=[6,1,4,3,2]$，$coins=10$。价格最低的四名英雄为 $1,2,3,4$，总价恰好为 $10$，按原数组顺序即为 $[1,4,3,2]$。若改买定价为 $6$ 的英雄，剩余点券最多再买两名较低价英雄（例如 $6+1+2=9$），只能得到 $3$ 名，数量更少。