/* 硬币题的解法，贪心算法，能AC，主要思路是统计当前硬币面值的总和sum，  * 然后从硬币数组里选取面值不小于sum+1的最大面值硬币加入，直到sum达到m；  * 之所以可以这样,我们借助测试用例{1,2,5,10}理解，  * 首先要凑出1，那么必选1，即{1}，选取面值不小于2的最大的2加入，即{1,2}，这时可凑出1,2,3；  * 现在sum为3，要选取不小于4的最大的加入，所以还是选2，即{1,2,2}，这时可凑出1,2,3,4,5；  * 现在sum为5，要选取不小于6的最大的加入，所以选5，即{1,2,2,5}，这时可凑出1~10；  * 现在sum为10，要选取不小于11的最大的加入，所以选10，即{1,2,2,5,10}，这时可凑出1~20；  * 此时sum达到20，循环停止。  * 通过以上可以分析出，假设目前我已有的硬币能凑出1~p范围内的所有数，  * 我们只需添加一个q，即可凑出1~(p+q)范围内的所有数。  */ import java.util.*; public class Exam1{          public static void main(String[] args) {         Scanner in = new Scanner(System.in);         int m = in.nextInt();         int n = in.nextInt();         int[] coin = new int[n];         //输入硬币数组；         for (int i = 0; i < n; i++) {             coin[i] = in.nextInt();         }         System.out.println(minNum(m,n,coin));     }          public static int minNum(int m, int n, int[] arr) {         //先把硬币数组排序，便于之后选出需要的最大的数；         Arrays.sort(arr);         //必须要有1，不然没法凑出1；         if(arr[0] != 1){             return -1;         }             int sum = 0;         int result = 0;                  while(true){             //总面值达到m即停止；             if(sum >= m){                 return result;             }           //依次从arr数组里选出符合要求的最大的数加入；             for(int i=n-1; i>=0; i--){                 if(arr[i] <= sum+1){                     //添加一枚硬币；                     sum += arr[i];                     result++;                     break;                 }             }         }     } }