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

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

# 解法一：80分 #

## 分析： ##

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

## 代码： ##

#include <iostream>
    #include <cstdio>
    using namespace std;
    
    int main()
    {
    #ifndef ONLINE_JUDGE
        freopen("order.in", "r", stdin);
        freopen("order.out", "w", stdout);
    #endif
    
        int n;
        cin >> n;
    
        if(0 == n)//班费为0元需要特判
        {
            cout << "0 0 0";
            return 0;
        }
    
        int lastMin = -1, ansI = 0, ansJ = 0, ansK = 0;
        for(int i = 0; i <= n/7; i++)
        {
            for(int j = 0; j <= n/4; j++)
            {
                int k = (n - 7 * i - 4 * j) / 3;
                if(k >= 0 && n == 7 * i + 4 * j + 3 * k)
                {
                    int Min = min(min(i, j), k); //可买多少套
                    if(Min > lastMin)
                    {
                        lastMin = Min;
                        ansI = i;
                        ansJ = j;
                        ansK = k;
                    }
                }
            }
        }
    
        if(-1 == lastMin)
        {
            cout << -1;
        }
        else
        {
            cout << ansI << ' ' << ansJ << ' ' << ansK;
        }
    
        return 0;
    }

## 运行结果： ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hhaXNodV96aGVuZw_size_16_color_FFFFFF_t_70]

## 运行超时原因分析： ##

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得到的总数量更多。

## 代码： ##

#include <iostream>
    #include <cstdio>
    using namespace std;
    
    int main(void)
    {
    #ifndef ONLINE_JUDGE
        freopen("order.in", "r", stdin);
        freopen("order.out", "w", stdout);
    #endif
    
        int n;
        cin >> n;
    
        if(0 == n)  //班费为0元时要特判
        {
            cout<<"0 0 0"<<endl;
            return 0;
        }
    
        for(int a = n / 14; a >= 0; a--)        //枚举最小值，即圆规的数量
        {
            for(int b = a; b <= n / 4; b++)      //枚举笔的数量
            {
                for(int c = a; c <= n / 3; c++) //枚举笔记本的数量
                {
                    if(a * 7 + b * 4 + c * 3 == n)
                    {
                        cout << a << " " << b << " " << c << endl;
                        return 0;
                    }
                }
            }
        }
    
        cout << "-1" << endl;   //无解
        return 0;
    }

了解信息学奥赛请加微信307591841或QQ群581357582

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hhaXNodV96aGVuZw_size_16_color_FFFFFF_t_70]: /images/20230528/e0e683fe725d45d3b47747b2e2023818.png