Description 卖方:这件商品14元 买方:给你20元 卖方:不好意思,我的零钱不够 买方:好吧,这是15元,剩的当小费 当到一个地方旅游时,如果你买东西的地方不支持信用,带零钱还是非常有用的。特别是有时候卖方没有零钱,如果你没有刚好的钱,你需要支付比卖价多一点。 当然你想付尽量少的钱(至少是商品价值的钱)。并且,当支付最少钱的时候,也最好是支付的硬币的数量最少。 Input 第一行包含一个整数表示测试数据的组数。每组测试数据每一行包含一个整数,表示你需要付的钱数,钱数不超过10000元。接下来包含一个整数n,表示你所拥有的钱的数量,n最多是100,接下来的n行每行一个整数,表示你有的每个硬币的面值,注意钱的面值可以是任意的,不和我们现在用的面值一样,钱的面值不超过10000元。 Output 对每组测试数据,在一行上输出两个整数:需要支付的钱数和数量。 Sample Input 1 1400 3 500 1000 2000 Sample Output 1500 2 本题的java代码
时间: 2023-06-13 22:04:38 浏览: 71
```java
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int t = sc.nextInt();
while (t-- > 0) {
int money = sc.nextInt();
int n = sc.nextInt();
int[] coins = new int[n];
for (int i = 0; i < n; i++) {
coins[i] = sc.nextInt();
}
Arrays.sort(coins); // 先排序,从小的硬币开始拿
int sum = 0, count = 0;
for (int i = n - 1; i >= 0; i--) { // 从大到小遍历硬币面值
while (sum + coins[i] <= money) { // 尽可能多的拿该硬币
sum += coins[i];
count++;
}
}
System.out.println(sum + " " + count);
}
sc.close();
}
}
```