文具订购

zltzlt

文具订购

题目描述

小明的班上共有 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[1000][3] = {}, i, j, k, id = 0, a_min[1000] = {}, min, am[1000][3] = {}, 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[id][0] = i;
                    ar[id][1] = j;
                    ar[id][2] = k;
                    id++;
                }
            }
    k = 1;

    // 最小值
    for (i = 0; i < id; i++)
    {
        min = (ar[i][0] < ar[i][1]) ? ar[i][0] : ar[i][1];
        a_min[i] = ((min < ar[i][2]) ? min : ar[i][2]);
    }

    // 最小值最大
    min = a_min[0];
    am[0][0] = ar[0][0];
    am[0][1] = ar[0][1];
    am[0][2] = ar[0][2];
    for (i = 1; i < id; i++)
    {
        if (a_min[i] > min)
        {
            min = a_min[i];
            for (j = 0; j < 1000; j++)
            {
                if (am[j][0] || am[j][1] || am[j][2]) // 不全是 0
                {
                    am[j][0] = 0;
                    am[j][1] = 0;
                    am[j][2] = 0;
                }
                else // 全是 0
                    break;
            }
            k = 1;
            am[0][0] = ar[i][0];
            am[0][1] = ar[i][1];
            am[0][2] = ar[i][2];
        }
        else if (a_min[i] == min)
        {
            am[k][0] = ar[i][0];
            am[k][1] = ar[i][1];
            am[k][2] = ar[i][2];
            k++;
        }
    }

    // 处理总和
    if (k == 1)
    {
        if (!(am[0][0] || am[0][1] || am[0][2])) // 无解
            cout << -1;
        else
            cout << am[0][0] << " " << am[0][1] << " " << am[0][2];
    }
    else
    {
        sum = am[0][0] + am[0][1] + am[0][2];

        for (i = 1; i < k; i++)
            if ((am[i][0] + am[i][1] + am[i][2]) > sum)
            {
                sum = am[i][0] + am[i][1] + am[i][2];
                sidx = i;
            }

        if (!(am[sidx][0] || am[sidx][1] || am[sidx][2])) // 无解
            cout << -1;
        else
            cout << am[sidx][0] << " " << am[sidx][1] << " " << am[sidx][2];
    }

    return 0;
}

一个账号

我竟然把 “刷题记录” 看成 “刷屏记录” 了。。。。