NOI Online入门组《文具订购》详细题解报告

短命女 2023-07-18 03:21 68阅读 0赞

解法一:80分

分析:

可采用暴力的方法,枚举圆规和笔的数量。笔记本的数量不要去枚举,直接计算即可。这样只需要两层循环即可。
两个地方需要注意:一是班费为0元时需要特别判断;二是最少可能购买0套,比如班费为3元时,答案是“0 0 3”。

代码:

  1. #include <iostream>
  2. #include <cstdio>
  3. using namespace std;
  4. int main()
  5. {
  6. #ifndef ONLINE_JUDGE
  7. freopen("order.in", "r", stdin);
  8. freopen("order.out", "w", stdout);
  9. #endif
  10. int n;
  11. cin >> n;
  12. if(0 == n)//班费为0元需要特判
  13. {
  14. cout << "0 0 0";
  15. return 0;
  16. }
  17. int lastMin = -1, ansI = 0, ansJ = 0, ansK = 0;
  18. for(int i = 0; i <= n/7; i++)
  19. {
  20. for(int j = 0; j <= n/4; j++)
  21. {
  22. int k = (n - 7 * i - 4 * j) / 3;
  23. if(k >= 0 && n == 7 * i + 4 * j + 3 * k)
  24. {
  25. int Min = min(min(i, j), k); //可买多少套
  26. if(Min > lastMin)
  27. {
  28. lastMin = Min;
  29. ansI = i;
  30. ansJ = j;
  31. ansK = k;
  32. }
  33. }
  34. }
  35. }
  36. if(-1 == lastMin)
  37. {
  38. cout << -1;
  39. }
  40. else
  41. {
  42. cout << ansI << ' ' << ansJ << ' ' << ansK;
  43. }
  44. return 0;
  45. }

运行结果:

在这里插入图片描述

运行超时原因分析:

n的最大值为10万,则最多需要循环10万/7 * 10万/4 ≈ 3.6亿次。运行次数过多导致超时。

解法二:100分

分析:

题目要求a,b,c的最小值尽可能大,所以就要让它们的最小值越接近n/14。
越好,如果a,b,c的最小值为n/14时无解,则尝试最小时为n/14-1的情景,如果仍然无解,则尝试最小值为n/14-2的情景,依此类推。

题目还要求a+b+c尽可能大。因为c最便宜,所以在成套的基础上,剩余的钱若能拆成c就尽量拆成c。若无法拆成c再考虑拆成b。
举两个例子:

例1:

若成套购买后还剩余12元,则12元可买3个b,也可买4个c,显然买4个c得到的总数量更多。

例2:

若成套购买后还剩余7元,则12元可买1个a,也可买1个b加上1个c,显然买1个b加上1个c得到的总数量更多。

代码:

  1. #include <iostream>
  2. #include <cstdio>
  3. using namespace std;
  4. int main(void)
  5. {
  6. #ifndef ONLINE_JUDGE
  7. freopen("order.in", "r", stdin);
  8. freopen("order.out", "w", stdout);
  9. #endif
  10. int n;
  11. cin >> n;
  12. if(0 == n) //班费为0元时要特判
  13. {
  14. cout<<"0 0 0"<<endl;
  15. return 0;
  16. }
  17. for(int a = n / 14; a >= 0; a--) //枚举最小值,即圆规的数量
  18. {
  19. for(int b = a; b <= n / 4; b++) //枚举笔的数量
  20. {
  21. for(int c = a; c <= n / 3; c++) //枚举笔记本的数量
  22. {
  23. if(a * 7 + b * 4 + c * 3 == n)
  24. {
  25. cout << a << " " << b << " " << c << endl;
  26. return 0;
  27. }
  28. }
  29. }
  30. }
  31. cout << "-1" << endl; //无解
  32. return 0;
  33. }
  34. 了解信息学奥赛请加微信307591841QQ581357582

发表评论

表情:
评论列表 (有 0 条评论,68人围观)

还没有评论,来说两句吧...

相关阅读

    相关 文具

    Problem Description bLue 带了 m 元钱去商店买文具,柜台上剩有 n 个文具套装,每个套装售价 ai 元,内含 bi 件相同种类的文具。 现在 b