文具订购

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 输出

1. -1

复制代码

样例 2 输入

1. 14

复制代码

样例 2 输出

1. 1 1 1

复制代码

样例 3 输入

1. 33

复制代码

样例 3 输出

1. 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 请大家指出，谢谢！

1. #include <iostream>
   
2. using namespace std;
   
3. 
   
4. int main()
   
5. {
   
6.     int n, a, ar[1000][3] = {}, i, j, k, id = 0, a_min[1000] = {}, min, am[1000][3] = {}, sidx = 0, sum;
   
7.     cin >> n;
   
8. 
   
9.     if (!(n % 14))
   
10.     {
    
11.         a = n / 14;
    
12.         cout << a << " " << a << " " << a;
    
13.         return 0;
    
14.     }
    
15.     if (!(n % 7))
    
16.     {
    
17.         a = n / 14 + 1;
    
18.         cout << (a - 1) << " " << a << " " << a;
    
19.         return 0;
    
20.     }
    
21.     if (!n)
    
22.     {
    
23.         cout << "0 0 0";
    
24.         return 0;
    
25.     }
    
26. 
    
27.     for (i = 0; i < 16; i++)         // a
    
28.         for (j = 0; j < 22; j++)     // b
    
29.             for (k = 0; k < 36; k++) // c
    
30.             {
    
31.                 if ((i * 7 + j * 4 + k * 3) == n)
    
32.                 {
    
33.                     ar[id][0] = i;
    
34.                     ar[id][1] = j;
    
35.                     ar[id][2] = k;
    
36.                     id++;
    
37.                 }
    
38.             }
    
39.     k = 1;
    
40. 
    
41.     // 最小值
    
42.     for (i = 0; i < id; i++)
    
43.     {
    
44.         min = (ar[i][0] < ar[i][1]) ? ar[i][0] : ar[i][1];
    
45.         a_min[i] = ((min < ar[i][2]) ? min : ar[i][2]);
    
46.     }
    
47. 
    
48.     // 最小值最大
    
49.     min = a_min[0];
    
50.     am[0][0] = ar[0][0];
    
51.     am[0][1] = ar[0][1];
    
52.     am[0][2] = ar[0][2];
    
53.     for (i = 1; i < id; i++)
    
54.     {
    
55.         if (a_min[i] > min)
    
56.         {
    
57.             min = a_min[i];
    
58.             for (j = 0; j < 1000; j++)
    
59.             {
    
60.                 if (am[j][0] || am[j][1] || am[j][2]) // 不全是 0
    
61.                 {
    
62.                     am[j][0] = 0;
    
63.                     am[j][1] = 0;
    
64.                     am[j][2] = 0;
    
65.                 }
    
66.                 else // 全是 0
    
67.                     break;
    
68.             }
    
69.             k = 1;
    
70.             am[0][0] = ar[i][0];
    
71.             am[0][1] = ar[i][1];
    
72.             am[0][2] = ar[i][2];
    
73.         }
    
74.         else if (a_min[i] == min)
    
75.         {
    
76.             am[k][0] = ar[i][0];
    
77.             am[k][1] = ar[i][1];
    
78.             am[k][2] = ar[i][2];
    
79.             k++;
    
80.         }
    
81.     }
    
82. 
    
83.     // 处理总和
    
84.     if (k == 1)
    
85.     {
    
86.         if (!(am[0][0] || am[0][1] || am[0][2])) // 无解
    
87.             cout << -1;
    
88.         else
    
89.             cout << am[0][0] << " " << am[0][1] << " " << am[0][2];
    
90.     }
    
91.     else
    
92.     {
    
93.         sum = am[0][0] + am[0][1] + am[0][2];
    
94. 
    
95.         for (i = 1; i < k; i++)
    
96.             if ((am[i][0] + am[i][1] + am[i][2]) > sum)
    
97.             {
    
98.                 sum = am[i][0] + am[i][1] + am[i][2];
    
99.                 sidx = i;
    
100.             }
     
101. 
     
102.         if (!(am[sidx][0] || am[sidx][1] || am[sidx][2])) // 无解
     
103.             cout << -1;
     
104.         else
     
105.             cout << am[sidx][0] << " " << am[sidx][1] << " " << am[sidx][2];
     
106.     }
     
107. 
     
108.     return 0;
     
109. }

复制代码

一个账号

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