题目描述
小明开了一家糖果店。
他别出心裁:把水果糖包成4颗一包和7颗一包的两种。
糖果不能拆包卖。
小朋友来买糖的时候,他就用这两种包装来组合。
当然有些糖果数目是无法组合出来的,比如要买 10 颗糖。
你可以用计算机测试一下,在这种包装情况下,最大不能买到的数量是17。
大于17的任何数字都可以用4和7组合出来。
本题的要求就是在已知两个包装的数量时,求最大不能组合出的数字。
输入格式
两个正整数 n,m,表示每种包装中糖的颗数。
输出格式
一个正整数,表示最大不能买到的糖数。
样例
数据范围
2≤n,m≤1000,
保证数据一定有解。
输入样例:
4 7
输出样例:
17
难度:简单
时/空限制:1s / 64MB
总通过数:1230
总尝试数:2056
来源:第四届蓝桥杯省赛C++A组,第四届蓝桥杯省赛JAVAC组
算法标签
算法1与算法二
() $O(n^2)$
时间复杂度
参考文献
Java 代码
import java.util.Arrays;
import java.util.Scanner;
public class MaiBuDao {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n=sc.nextInt();
int m=sc.nextInt();
System.out.println("自己的方法:"+f1(n,m));
System.out.println("别人的方法:"+f2(n,m));
}
public static int f1(int n,int m) {
int min = Math.min(n,m),max=Math.max(n, m),step=0,result=min-1;//max和min变量是为了对m,n进行一个排序。step记录连续的能被组成的数的个数。
for(int i=2;i<=min;i++)if(m%i==0&&n%i==0)return -1;//如果两个数都是一个基数的倍数,那么这两个数将不能合成任何数
//上面一行可以改为if(!JudgeGcd(n,m))return -1;因为上面一行相当于暴力求两个数是否互质
//如任意两个偶数不能合成奇数数 3 6,6 9,9 12等等将至少不能合成3^n与3^(n+1)之间的数。
int[] arr = new int[max];
//对于循环数组实现的队列
//在队列中,第i个值要存放到的下标为(i-1)%length
//第i个值往前移动n个位置的值对应的下标为(i-1-n+length)%length,加上一个length是为了防止i-1-n出现负数。如果i-1>=n,则只需(i-1-n)
//故第i个值往前移动length个位置对应的下标为(i-1-length+length)%length==(i-1)%length,不需要考虑i-1是大于还是小于length
for(int i=min;;i++) {
if(step>=min)break;
if(i==min||arr[(i-1-min)%max]==1||i==max||i>max&&arr[(i-1)%max]==1) {
arr[(i-1)%max]=1;step++;
}
else {
step=0;result=i;
}
}
return result;
}
//后来看了别人的答案,原来是有定理证明的
/*
* 1.若两数互质将无解
* 2.若不互质则将有解,且解为ab-a-b;
*/
public static int f2(int n,int m) {
if(!JudgeGcd(n,m))return -1;
else return n*m-n-m;
}
public static boolean JudgeGcd(int a,int b) {//辗转相除法判断两个数是否互质
int r=0;
do {
r=a%b;//如果b>a,执行一遍循环体将导致a>b
a=b;
b=r;
}while(r!=0);
if(a==1)return true;//如果a==1证明a,b互质
else return false;
}
}
算法2
(动态规划-完全背包) $O(n^2)$
不推荐用这个方法,太浪费内存了。
时间复杂度
参考文献
C++ 代码
import java.util.Scanner;
class Main{
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n=sc.nextInt();
int m=sc.nextInt();
System.out.println(dp(n,m));
}
public static int dp(int ...arr) {
int N=1000000,result=0;
int[] biao=new int[N];//因为上一行的记录提供子问题的解之后将再也没用,因此可以覆盖
biao[0]=1;
for(int i=1;i<=arr.length;i++) {
for(int j=arr[i-1];j<N;j++) {
if(biao[j]==1)continue;
else biao[j]=biao[j-arr[i-1]];
}
}
for(int j=1;j<N;j++)if(biao[j]==0)result=j;
return result;
}
}