题目背景：
小Q去商场购物，经常会遇到找零的问题。
小Q现在手上有n种不同面值的硬币，每种面值的硬币都有无限多个。
为了方便购物，小Q希望带尽量少的硬币，并且要能组合出1到m之间（包含1和m）的所有面值。
输入格式
第一行包含两个整数m和n。
接下来n行，每行一个整数，第 i+1 行的整数表示第 i 种硬币的面值。
输出格式
输出一个整数，表示最少需要携带的硬币数量。
【2019腾讯笔试题】如果无解，则输出-1。
import java.util.*;
public class 小Q购物 {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int m = sc.nextInt();
//要求面值
int n = sc.nextInt();
//面值种类
int[] arr = new int[n+1];
for(int i = 0;
i < n;
i++){
arr[i] = sc.nextInt();
}
Arrays.sort(arr, 0, n);
if(arr[0] != 1){
System.out.println(-1);
}else{
// 忽略面值超出要求面值
while(n > 0 && arr[n-1] > m) n--;
arr[n] = m+1;
int res = 0;
for(int i = 0, s = 0;
i < n;
i++){
//
int k = (arr[i+1]-1-s+ arr[i]-1)/arr[i];
res += k;
s += k*arr[i];
}
System.out.println(res);
}
}
}
