2019春季暑期实习生正式批招聘笔试【腾讯】（回忆版）第二题

问题描述

现在 康康 手上有 n 种不同面值的硬币，每种硬币有无限多个。为了方便购物，他希望带尽量少的硬币，但是要能组合出 1 到 m 之间的任意值。

输入格式

第一行为两个整数：m 和 n，他们的意义如题目描述。
接下来的 n 行，每行一个整数，第 i+1 行的整数表示第 i 种硬币的面值

输出格式

最少需要携带的硬币数量，如果无解则输出-1。

样例输入

20 4
1
2
5
10

样例输出

5

解题代码

import java.util.Arrays; import java.util.Scanner;public class Main {public static void main(String[] args) {int sum = 0;int ans = 0;Scanner scanner = new Scanner(System.in);int m = scanner.nextInt();int n = scanner.nextInt();int[] list = new int[n + 1];for (int i = 1; i <= n; i++) {list[i] = scanner.nextInt();}Arrays.sort(list);if (list[1] != 1) {System.out.print(-1);}while (true) {if (sum >= m) {System.out.println(ans);break;}for (int i = n; i >= 1; i--) {if (list[i] <= sum + 1) {sum += list[i];ans++;break;}}}} }

结果

总结

以上是生活随笔为你收集整理的2019春季暑期实习生正式批招聘笔试【腾讯】（回忆版）第二题的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。