【每日蓝桥】50、一七年省赛Java组真题“包子凑数”

你好呀，我是灰小猿，一个超会写bug的程序猿！

欢迎大家关注我的专栏“每日蓝桥”，该专栏的主要作用是和大家分享近几年蓝桥杯省赛及决赛等真题，解析其中存在的算法思想、数据结构等内容，帮助大家学习到更多的知识和技术！

标题：包子凑数

小明几乎每天早晨都会在一-家包子铺吃早餐.他发现这家包子铺有N种蒸笼,其中第i种蒸

笼恰好能放Ai个包子.每种蒸笼都有非常多笼，可以认为是 无限笼.

每当有顾客想买X个包子，卖包子的大叔就会迅速选出若干笼包子来，使得这若干笼中恰

好一共有X个包子.比如一共有3种蒸笼，分别能放3. 4和5个包子.当顾客想买11个

包子时,大叔就会选2笼3个的再加1笼5个的(也可能选出1笼3个的再加2笼4个的).

当然有时包子大叔无论如何也凑不出顾客想买的数量.比如一-共有3种蒸笼，分别能放4.

5和6个包子.而顾客想买7个包子时，大叔就凑不出来了.

小明想知道一共有多少种数目是包子大叔凑不出来的。

 

输入

第- -行包含-一个整数N. (1<=N<= 100)

以下N行每行包含-一个整数Ai. (1<= Ai<= 100)

输出

一个整数代表答案.如果凑不出的数目有无限多个，输出INF.

例如,

输人:

2

4

5

程序应该输出:

6

 

再例如输入：

2

4

6

程序应该输出：

INF

 

样例解释

对于样例1，凑不出的数目包括：1, 2, 3, 6, 7, 11。
对于样例2，所有奇数都凑不出来，所以有无限多个。

 

【资源约定】

峰值内存消耗(含虚拟机) < 256M

CPU消耗< 1000ms

请严格按要求输出，不要画蛇添足地打印类似: " 请您输人..”的多余内容.

所有代码放在同一个源文件中，调试通过后，拷贝提交该源码.

不要使用package语句。不要使用jdk1.7及以上版本的特性.

主类的名字必须是: Main, 否则按无效代码处理.

提交程序时，注意选择所期望的语言类型和编译器类型.

解题思路：

本题在求解上用到的思想与完全背包问题类似，同时在2013年也有一道类似的题目叫“买不到的数目”，像了解的小伙伴可以看我的这篇文章“【每日蓝桥】9、一三年省赛Java组真题“买不到的数目””，

本题的求解首先需要搞清楚一个定理：互为质数的两个数a和b，最大不能组成的数n=a*b-a-b

如果两个数不互质，则最大不能组成的数无上限，

所以在本题求解的时候，我们知道包子数最大是100，所以最大不能组成的数最大也是100*100-100-100=9800

那么我们其实可以判断输入的数是否互质，如果互质（即最大公约数等于1）则例举出0~10000以内所有能凑出的数，然后再得出不能凑出的数的个数，

如果输入的数不互质（即最大公约数不等于1），那么说明最大不能凑成的数无上限，直接输出INT即可。

对于如何找出0~10000以内所有能凑出的数，可以使用类似于动态规划的思想，利用布尔型数组将能凑出的数标记为true，不能则记为false，最后统计标记为false的数的个数即可。

答案源码：

   

    

     

      

     
     

      

       package 一七年省赛真题;
      
     
    

     

      

     
     

      
 
      
     
    

     

      

     
     

      

       import java.util.Scanner;
      
     
    

     

      

     
     

      
 
      
     
    

     

      

     
     

      
 
      
     
    

     

      

     
     

      

       public 
       class Year2017_Bt8 {
      
     
    

     

      

     
     

      
 
      
     
    

     

      

     
     

      
	
       static 
       int ans;
      
     
    

     

      

     
     

      
	
       static 
       int g;
      
     
    

     

      

     
     

      
	
       static 
       boolean []arr = 
       new 
       boolean[
       10100];	
       //记录0~10000中的数是否能被凑出,在这里将数组长度定义的长一点
      
     
    

     

      

     
     

      
	
       public static void main(String[] args) {
      
     
    

     

      

     
     

      

       		Scanner scanner = 
       new Scanner(System.in);
      
     
    

     

      

     
     

      
		
       int N = scanner.nextInt();
      
     
    

     

      

     
     

      
		
       int [] a = 
       new 
       int[N];
      
     
    

     

      

     
     

      

       		arr[
       0] = 
       true;
       //表示0是可以凑出来的，即一个都不买
      
     
    

     

      

     
     

      
		
       for (
       int i = 
       0; i < N; i++) {
      
     
    

     

      

     
     

      

       			a[i] = scanner.nextInt();
      
     
    

     

      

     
     

      
			
       if (i==
       0) g = a[i];
      
     
    

     

      

     
     

      

       			g = gcd(g,a[i]);
       //求最大公约数
      
     
    

     

      

     
     

      
			
      
     
    

     

      

     
     

      
			
       for (
       int j = 
       0; j < 
       10000; j++) {
      
     
    

     

      

     
     

      
				
       //如果当前的数是可以被凑出来的，那么这个数加上刚刚输入的数也一定是可以被凑出来的。
      
     
    

     

      

     
     

      
				
       if (arr[j]) arr[j+a[i]]=
       true;
      
     
    

     

      

     
     

      

       			}
      
     
    

     

      

     
     

      

       		}
      
     
    

     

      

     
     

      
		
       //如果说所有的数输入完之后，得到的最大公约数不是1，说明不互质
      
     
    

     

      

     
     

      
		
       //如果数不互质，则有无限多个数凑不出来
      
     
    

     

      

     
     

      
		
       if (g!=
       1) {
      
     
    

     

      

     
     

      

       			System.out.println(
       "INF");
      
     
    

     

      

     
     

      
			
       return ;
      
     
    

     

      

     
     

      

       		}
      
     
    

     

      

     
     

      
		
      
     
    

     

      

     
     

      
		
       //找出0~10000之内所有不能被凑出的数
      
     
    

     

      

     
     

      
		
       for (
       int i = 
       0; i < 
       10000; i++) {
      
     
    

     

      

     
     

      
			
       if(!arr[i]) {
      
     
    

     

      

     
     

      

       				ans++;
      
     
    

     

      

     
     

      

       			}
      
     
    

     

      

     
     

      

       		}
      
     
    

     

      

     
     

      

       		System.out.println(ans);	
      
     
    

     

      

     
     

      
 
      
     
    

     

      

     
     

      

       	}
      
     
    

     

      

     
     

      
	
      
     
    

     

      

     
     

      
	
       /**
      
     
    

     

      

     
     

      

        * 求两个数的最大公约数
      
     
    

     

      

     
     

      

        * */
      
     
    

     

      

     
     

      
	
       private static int gcd(int a, int b) {
      
     
    

     

      

     
     

      
		
       if(b==
       0) 
       return a;
      
     
    

     

      

     
     

      
		
       return gcd(b, a%b);
      
     
    

     

      

     
     

      

       	}
      
     
    

     

      

     
     

      
 
      
     
    

     

      

     
     

      
 
      
     
    

     

      

     
     

      
 
      
     
    

     

      

     
     

      

       }
      
     
   

输出样例：

其中有不足或者改进的地方，还希望小伙伴留言提出，一起学习！

感兴趣的小伙伴可以关注专栏！

灰小猿陪你一起进步！