P1012 文具采购

题目描述

禾木的班上共有 n 元班费，同学们准备使用班费集体购买 3 种物品：

1. 圆规，每个 7 元。
2. 笔，每支 4 元。
3. 笔记本，每本 3 元。

禾木负责订购文具，设圆规，笔，笔记本的订购数量分别为 a,b,c，他订购的原则依次如下：

1. n 元钱必须正好用光，即 7a+4b+3c=n。
2. 在满足以上条件情况下，成套的数量尽可能大，即 a,b,c 中的最小值尽可能大。
3. 在满足以上条件情况下，物品的总数尽可能大，即 a+b+c 尽可能大。

请你帮助禾木求出满足条件的最优方案。可以证明若存在方案，则最优方案唯一。

思路

直接算肯定TLE，这是三层嵌套，10的5次方，100000 * 100000 * 100000 = 1000000000000000，1百万亿，加上简单简化，也不太行。

这里就不说普通解法了。

题目要求a，b，c的最小值尽可能大，所以就要让它们的最小值越接近n/14越好。如果a，b，c的最小值为n/14 时无解，则让a,b,c的最小值为n/14−1，以此类推，直到有解为止；

这样一下数据缩了好多，之后再用普通解法就可以了

    for(int a = n / 14;a >= 0;a--)
    for(int b = a;b <= n / 3;b++)
    for(int c = a;c <= n / 3;c++)

在加上一个判断：

if(7 * a + 4 * b + 3 * c == n)
                {
                    cout << a << " " << b << " " << c << endl;
                    return 0;
                }

和成一下。

参考代码：

#include <iostream>//hetao3097453
using namespace std;
bool flag = false;
int main()
{
    int n;
    cin >> n;
    for(int a = n / 14;a >= 0;a--)
    {
        for(int b = a;b <= n / 3;b++)
        {
            for(int c = a;c <= n / 3;c++)
            {
                if(7 * a + 4 * b + 3 * c == n)
                {
                    cout << a << " " << b << " " << c << endl;
                    return 0;
                }
            }
        }
    }
    cout << "-1";
    return 0;
}

hetao3097453

2023年3月26日