题目描述

小明的班上共有 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∼6：n≤14。
对于测试点 7∼12：n 是 14 的倍数。
对于测试点 13∼18：n≤100。
对于所有测试点：0≤n≤105。

样例

输入样例 : 33
输出样例 : 1 2 6

算法1 扩展欧几里得

(暴力枚举) $O(n)$

因为这里$7 = 3 + 4$, 那么原来的$7a+4b+3c=n$就可以转换成$3a+4b=n$
而题目里的限制条件主要有两个,

条件1 : 使得a + b + c最大

这里我们使用扩展欧几里得算法求得b的最小正整数解, 因为同样的班费买3元的物品肯定是要比买4元的多

条件2 : 最大化min(a, b, c)

那么在求得b的最小正整数解之后, 由于$a,b$互质让$a$每次减4, $b$每次加3, 循环就可以得出结果
对于7元的物品$c$来说, 只需要让$a$和$b$每次减1即可

C++ 代码

#include <iostream>
#include <algorithm>
using namespace std;

int n;
int a, b, c;
bool has_ans;


int exgcd(int a, int b, int& x, int& y)
{
    if(!b)
    {
        x = 1, y = 0;
        return a;
    }
    int d = exgcd(b, a % b, y, x);
    y -= a / b * x;
    return d;
}

void work(int& x, int& y)
{
    int minv = min(x, y);
    while(x >= 0 && y >= 0)
    {
        int t1 = x - 4, t2 = y + 3;
        if(min(t1, t2) > minv && t1 >= 0 && t2 >= 0)
        {
            minv = min(t1, t2);
            x = t1, y = t2;
        }
        else break;
    }
}

int main()
{
    cin >> n;
    // exgcd求出最小整数解
    int d = exgcd(3, 4, a, b);          // 因为3, 4 互质所以d必然为1
    // a + b要最大, 那么只要使b最小, 这是因为物品a只需要3元, 物品b需要4元, 所以同样班费可以购买更多a

    b *= n;
    int b_min = (b % 3 + 3) % 3;        // 处理负数
    a = (n - 4 * b_min) / 3;
    b = b_min;

    //  接下来要满足条件2, 最大化min(a, b, c)
    work(a, b);

    if(a >= 0 && b >= 0) has_ans = true;

    // 对于7元的物品可以由3和4拼凑出来
    for(; a > 0 && b > 0 && min(a ,b) > c + 1; a--, b--, c++) ;

    if(!has_ans) cout << -1 << endl;
    else cout << c << ' ' << b << ' ' << a << endl;
    return 0;
}

算法2 互质的数所不能表示的最小整数

(暴力枚举)

因为$(3, 4)==1$, 所以3和4所不能表示的最小的整数为$(3-1)*(4-1)-1=5$
同样地1和2也不可以被表示
那么我们可以先成套地购买, 一套花费14元
当$n-14k \ != 1,2,5$时, 迭代k就可以找出答案了

C++ 代码

#include <iostream>
#include <cstring>
using namespace std;

int n;

int main()
{
    cin >> n;
    if(n == 1 || n == 2 || n == 5) cout << -1 << endl;
    else
    {
        for(int k = n / 14; k >= 0; --k)
        {
            int s = n - 14 * k;
            if(s == 1 || s == 2 || s == 5) continue;
            else
            {
                for(int c = s / 3; c >= 0; --c)
                    for(int b = (s - 3 * c) / 4; b >= 0; --b)
                    {
                        if(s - 3 * c - 4 * b == 0)
                        {
                            cout << k << ' ' << k + b << ' ' << k + c << endl;
                            return 0;
                        }
                    }
                break;
            }
        }
    }
    return 0;
}