蓝桥杯2013年第四届真题-买不到的数目-题解（Java代码）

解题思路:

//例如a=4 b=7,
           //第一次购买就二种情况，要么是4，要么是7
           //第二次购买三种，要么是4+4=8，4+7=11，7+7=14
           //第三次购买六种 ，要么是8+4=12，8+7=15，11+4=16，11+7=18，14+4=18，14+7=21
           //第四次购买十种 ，要么是12+4=16，12+7=19，15+4=19，15+7=22，16+4=20，16+7=23，18+4=22，18+7=25，21+4=25，21+7=28
           //第五次购买十种 ，要么是16+4=20，16+7=23，19+4=23，19+7=26，22+4=26，22+7=29，20+4=24，20+7=27，23+4=27，23+7=30，25+4=29，25+7=32，28+4=32，28+7=35
           //你会发现有15，16，18，19，20，21，22，23，24，25，26，27，28，29，30，就是没有17，所以17就是买不到的数目，而且每一个数都只会加a或者加b，

          //刚刚好和数组很像，所以用数组来记录他们的数字。所以每组合一次就s++一次，一直到大于a和b的最大数

注意事项:

参考代码:

  import java.util.Arrays;
    import java.util.Scanner;
    public class Main01 {
        public static void main(String[] args) {
            Scanner scanner=new Scanner(System.in);
            int a=scanner.nextInt();
            int b=scanner.nextInt();
            int max=Math.max(a, b);//两个数的最大值
            int[]arr=new int[9999];//用来动态规划里面那些可以组合的数字
           
            arr[a]=1;
            arr[b]=1;
            int k=0;//用来记录不能组合的数字
            int s=0;//用来统计可以组合的数字的个数(注意：这里用来统计可以组合的数字一旦遇到不能组合的数字将会重置)
            for (int i = 1; i < arr.length; i++) {
                if (arr[i]==0) {//如果不能组合那么就获取这个数并且重置可以组合的数字的个数
                    k=i;
                    s=0;
                }else {//如果可以组合那么i+a和i+b的数字也一定可以组合
                    arr[i+a]=1;
                    arr[i+b]=1;
                    s++;//可以组合则s++
                }
                if (s>=max) {//一旦可以组合数字个数大于等于了a和b的最大值将退出循环
                    break;
                }
            }
            System.out.println(k);
        }
    }