2019腾讯笔试题

题目背景：
小Q去商场购物，经常会遇到找零的问题。

小Q现在手上有n种不同面值的硬币，每种面值的硬币都有无限多个。

为了方便购物，小Q希望带尽量少的硬币，并且要能组合出1到m之间（包含1和m）的所有面值。

输入格式
第一行包含两个整数m和n。

接下来n行，每行一个整数，第 i+1 行的整数表示第 i 种硬币的面值。

输出格式
输出一个整数，表示最少需要携带的硬币数量。

如果无解，则输出-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);
        }
    }
}