题目描述
小明开了一家糖果店。
他别出心裁:把水果糖包成4颗一包和7颗一包的两种。
糖果不能拆包卖。
小朋友来买糖的时候,他就用这两种包装来组合。
当然有些糖果数目是无法组合出来的,比如要买 10 颗糖。
你可以用计算机测试一下,在这种包装情况下,最大不能买到的数量是17。
大于17的任何数字都可以用4和7组合出来。
本题的要求就是在已知两个包装的数量时,求最大不能组合出的数字。
算法1
(暴力枚举) $O(n^2)$
暴力枚举每种 N = ip + j q的情况
C++ 代码
#include <iostream>
using namespace std;
const int N = 312119;
bool ans[N]; //ans[i]为true时 代表i可以用 p 和 q 组合出来
int main(){
int p, q;
cin >> p >> q;
// i*p + j*q = N
for(int i=0; i*p<=N;i++){
for(int j=0; i*p+j*q<=N;j++){
ans[i*p+j*q] = true;
}
}
//在已知两个包装的数量时,求最大不能组合出的数字
for(int i = N;i>=2;i--){
if(!ans[i]){
cout << i;
return 0;
}
}
return 0;
}
算法2
数学公式
p*q - p -q
C++ 代码
#include <iostream>
using namespace std;
int main(){
int p, q;
cin >> p >> q;
cout << p*q -p-q << endl;
return 0;
}