题目描述
小明的班上共有 n n n 元班费,同学们准备使用班费集体购买 3 3 3 种物品:
- 圆规,每个 7 7 7 元。
- 笔,每支 4 4 4 元。
- 笔记本,每本 3 3 3 元。
小明负责订购文具,设圆规,笔,笔记本的订购数量分别为 a , b , c a,b,c a,b,c,他订购的原则依次如下:
- n n n 元钱必须正好用光,即 7 a + 4 b + 3 c = n 7a+4b+3c=n 7a+4b+3c=n。
- 在满足以上条件情况下,成套的数量尽可能大,即 a , b , c a,b,c a,b,c 中的最小值尽可能大。
- 在满足以上条件情况下,物品的总数尽可能大,即 a + b + c a+b+c a+b+c 尽可能大。
请你帮助小明求出满足条件的最优方案。可以证明若存在方案,则最优方案唯一。
分析
做法:暴力加乱搞
我们可以枚举圆规和笔的数量,在算出笔记本的数量,如果剩下的钱不能整除笔记本的钱 3 3 3 则不可行,否则更新答案。
注意数量要从 0 0 0 开始枚举。
代码
#include <bits/stdc++.h>
#define int long long
using namespace std;
int n, maxn = -1, sum, a, b, c;
signed main(){
cin >> n;
for(int i = 0; i <= n / 7; i ++){
for(int j = 0; j <= n / 4; j ++){
if((n - 7 * i - 4 * j) % 3 != 0){
continue;
}
int k = (n - 7 * i - 4 * j) / 3;
if(min(i, min(j, k)) > maxn){
maxn = min(i, min(j, k)), sum = i + j + k, a = i, b = j, c = k;
}else if(min(i, min(j, k)) == maxn && i + j + k > sum){
maxn = min(i, min(j, k)), sum = i + j + k, a = i, b = j, c = k;
}
}
}
if(maxn == -1){
cout << -1;
}else{
cout << a << " " << b << " " << c;
}
return 0;
}