文具订购
本帖最后由 zltzlt 于 2020-3-9 17:37 编辑文具订购
题目描述
小明的班上共有 n 元班费，同学们准备使用班费集体购买 3 种物品：
[*]圆规，每个 7 元。
[*]笔，每支 4 元。
[*]笔记本，每本 3 元。
小明负责订购文具，设圆规，笔，笔记本的订购数量分别为 a,b,c，他订购的原则依次如下：
[*]n 元钱必须正好用光，即 7a+4b+3c=n。
[*]在满足以上条件情况下，成套的数量尽可能大，即 a,b,c 中的最小值尽可能大。
[*]在满足以上条件情况下，物品的总数尽可能大，即 a+b+c 尽可能大。
请你帮助小明求出满足条件的最优方案。可以证明若存在方案，则最优方案唯一。
输入格式
仅一行一个整数 n 表示班费数量。
输出格式
若方案不存在则输出 -1。否则输出一行三个用空格分隔的非负整数 a,b,c 表示答案。
样例 1 输入
1
样例 1 输出
-1
样例 2 输入
14
样例 2 输出
1 1 1
样例 3 输入
33
样例 3 输出
1 2 6
样例 3 解释
a=2,b=4,c=1 也是满足条件 1，2 的方案，但对于条件 3，该方案只买了 7 个物品，不如 a=1,b=2,c=6 的方案。
数据范围与提示
对于测试点 1 ～ 6：n ≤ 14。
对于测试点 7 ～ 12：n 是 14 的倍数。
对于测试点 13 ～ 18：n ≤ 100。
对于所有测试点：0 ≤ n ≤ 105。
时间限制
1.0s
空间限制
256MB
我的解答
有 Bug 请大家指出，谢谢！
#include <iostream>
using namespace std;
int main()
{
int n, a, ar = {}, i, j, k, id = 0, a_min = {}, min, am = {}, sidx = 0, sum;
cin >> n;
if (!(n % 14))
{
a = n / 14;
cout << a << " " << a << " " << a;
return 0;
}
if (!(n % 7))
{
a = n / 14 + 1;
cout << (a - 1) << " " << a << " " << a;
return 0;
}
if (!n)
{
cout << "0 0 0";
return 0;
}
for (i = 0; i < 16; i++) // a
for (j = 0; j < 22; j++) // b
for (k = 0; k < 36; k++) // c
{
if ((i * 7 + j * 4 + k * 3) == n)
{
ar = i;
ar = j;
ar = k;
id++;
}
}
k = 1;
// 最小值
for (i = 0; i < id; i++)
{
min = (ar < ar) ? ar : ar;
a_min = ((min < ar) ? min : ar);
}
// 最小值最大
min = a_min;
am = ar;
am = ar;
am = ar;
for (i = 1; i < id; i++)
{
if (a_min > min)
{
min = a_min;
for (j = 0; j < 1000; j++)
{
if (am || am || am) // 不全是 0
{
am = 0;
am = 0;
am = 0;
}
else // 全是 0
break;
}
k = 1;
am = ar;
am = ar;
am = ar;
}
else if (a_min == min)
{
am = ar;
am = ar;
am = ar;
k++;
}
}
// 处理总和
if (k == 1)
{
if (!(am || am || am)) // 无解
cout << -1;
else
cout << am << " " << am << " " << am;
}
else
{
sum = am + am + am;
for (i = 1; i < k; i++)
if ((am + am + am) > sum)
{
sum = am + am + am;
sidx = i;
}
if (!(am || am || am)) // 无解
cout << -1;
else
cout << am << " " << am << " " << am;
}
return 0;
} 我竟然把 “刷题记录” 看成 “刷屏记录” 了。。。。
页:
[1]