nowcode-HJ-98

HJ98 自动售货系统

1 题目描述

• 题目链接：HJ98 自动售货系统

  实现一个自动贩卖机程序编写，其中售货机中有6种货物,其单价依次为$\{2, 3, 4, 5, 8, 6\}$. 商品编号从1开始，商品名为A+编号构成，即商品列表为$\{A1, A2, A3, A4, A5, A6\}$.

  售货机只接受1元、2元、5元以及10元四种面额的纸币, 因而售货机中存钱盒也只有这四种面额的钱币。

  编写程序，实现以下功能：

• 初始化：
  • 命令格式：r A1数量-A2数量-A3数量-A4数量-A5数量-A6数量 1元张数-2元张数-5元张数-10元张数
  • 初始化后返回S001:Initialization is successful表示初始化完成
• 投币
  • 命令格式：p 钱币面额
  • 若投入纸币不是1、2、5、10面额，则抛出错误信息E002:Denomination error;
  • 若投入5或10元钱币，而存钱盒中1元和2元的总金额小于投入的钱币面额，则抛出错误信息E003:Change is not enough, pay fail；
  • 如果自动售货机中物品全部卖光，则抛出错误信息E005:All the goods sold out；
  • 除去以上情况则视为投币成功，返回S002:Pay success,balance=X, 其中X表示当前剩余的金额。
• 购买
  • 命令格式：b 商品名称
  • 如果购买商品不在列表中，抛出错误信息E006:Goods does not exist；
  • 如果该商品已经卖完，抛出错误信息E007:The goods sold out;
  • 如果剩余金额小于该货物价格，抛出错误信息E008:Lack of balance;
  • 除去以上情况视为购买成功，更新当前剩余金额并返回S003:Buy success,balance=X。
• 退币
  • 命令格式：c
  • 若剩余金额等于0，抛出错误信息E009:Work failure;
  • 若剩余金额大于0，则进行找零。
    • 退币原则：如果够找零，则按找回纸币张数最小的方案执行；否则尽可能让用户损失少一点。
• 查询
  • 命令格式：q 查询类别
  • 查询类别为1则查询存钱盒信息，为0则查询货物信息. 如果查询类别出错，则抛出错误信息E010:Parameter error；
  • 查询货物信息需要按货物剩余数量降序后输出，如果数量相同则按货物编号输出，货物编号小者先输出，输出格式为商品名 价格 数量.
  • 查询存钱盒信息则按货币面额从小到大输出，输出格式为面额 yuan coin number=纸币数量.

输入描述：

依照说明中的命令码格式输入命令。

输入描述：

输出执行结果。

示例1：

输入: r 22-18-21-21-7-20 3-23-10-6;c;q0;p 1;b A6;c;b A5;b A1;c;q1;p 5;
输出: S001:Initialization is successful
    E009:Work failure
    E010:Parameter error
    S002:Pay success,balance=1
    E008:Lack of balance
    1 yuan coin number=1
    2 yuan coin number=0
    5 yuan coin number=0
    10 yuan coin number=0
    E008:Lack of balance
    E008:Lack of balance
    E009:Work failure
    E010:Parameter error
    S002:Pay success,balance=5

2 思路

  截取输入字符串为若干个命令，并按照命令的第一个字符进行不同的操作。货物信息和存钱盒信息均用数组来存储。主要就是进行模拟，过程不难，就是细节要注意，其中尤其是命令行中首字符要接空格，如果不接空格，则需要抛出错误信息(题目中只有查询指令需要进行这个检测)。

  其中最主要的是找零和查询货物信息。

• 找零：在能够完全找开的情况下要找出钱币张数最少的方案并进行输出，这个直接通过贪心即可实现，但是可能存在存钱盒中为1 3 1 0,而金额为7,此时优先选择面额为5，然后就找不开了。所以按照贪心找零后需要对余额进行判断。会找不开零钱，其实就是因为钱币5的存在。分成几种种情况：
   
  • 如果用了5，此时最后的零钱为0-4，0不用考虑(此时能找零并且已经钱币张数最少);为1时，如果此时没有1的零钱，但有很多2的零钱，那么此时就不应选择5，而是换成3张2；为2时，只能是没有2而1的数量小于2,这时候就是没法找出零，只能直接返回(此时已经是用户损失最少的方案)；为3时，说明有2没1或没2有1但1的数量很少，前一种方案需要考虑是否将5换成2，而后一种则直接无法找零；为4时，零钱数量为1 1、<3 0、0 <2这几种情况，其实就是没法找零，返回。
     
  • 而当没有用5，则说明零钱就是不够找，当前的方案就是最优解。
     
  • 其实就是主要因为1的数量少，而如果用了5会出现剩余金额为奇数导致找不开的情况；或是本身零钱就少而导致找不开。因此，考虑钱币2的数量，当找完零2的总面额大于5则说明此时有比目前更好的方案(实现完全找零或者用户损失最少的方案),则将5兑成2。
     
• 查询货物信息：需要按照货物数量进行降序输出，而当两种货物数量一样则按编号进行输出，那么可以用一个数组来表征下标，然后通过引用的方式并运用lambda表达式进行排序，这里不直接对货物进行排序，而是对下标数组进行排序。

#include <iostream>     // cin、cout
#include <vector>       // vector容器
#include <algorithm>    // find、sort
#include <string>       // string容器
#include <numeric>      // iota
#include <string.h>     // memset

using namespace std;    

int  coins[4];                          // 存钱盒信息
int things[6];                          // 货物信息
int  prize[6] = {2, 3, 4, 5, 8, 6};     // 货物价格
int   cash[4] = {1, 2, 5, 10};          // 钱币面额
int   balance = 0;                      // 当前金额

// 实现初始化
void systemInit(const string str){
    // 从下标1开始，跳过命令行第一个字符
    int pos = 1, len = str.length(), cnt = 0;
    // 找货物信息的起始位置
    while(pos < len && str[pos]==' ')
        ++pos;
    // 找货物信息和存钱盒信息的分割点
    int idx = find(str.begin() + pos, str.end(), ' ') - str.begin();
    // 分割命令行，这里存钱盒其实可以加一个检测开头是否为空格
    string t = str.substr(pos, idx), c = str.substr(idx + 1);
    // 初始化货物数量
    len = t.length(), idx = 0;
    for (int i = 0; i <= len; ++i){
        if(i == len || t[i] == '-'){
            things[idx++] = cnt;    // 数量
            cnt = 0;
        }else{
            cnt += t[i] - '0';
        }
    }
    // 初始化存钱盒各种钱币数量
    len = c.length(), idx = 0;
    for (int i = 0; i <= len; ++i){
        if(i == len || c[i] == '-'){
            coins[idx++] = cnt;    // 数量
            cnt = 0;
        }else{
            cnt *= 10;
            cnt += c[i] - '0';
        }
    }
    cout << "S001:Initialization is successful" << endl;
}

// 实现投币功能
void cashIn(const string str){
    int len = str.length(), pos = 1, cnt = 0;
    // 找到钱币在字符串中的起始位置
    while (pos < len && str[pos] == ' ')
        ++pos;
    // 获取钱币金额
    while(pos < len && str[pos] >= '0' && str[pos] <= '9'){
        cnt *= 10;
        cnt += str[pos++] - '0';
    }
    // 检测货物是否已经完全卖完
    for (int i = 0; i < 6; ++i){
        if(things[i] != 0){
            break;
        }else if(i == 5){
            cout << "E005:All the goods sold out" << endl;
            return; // 卖完则直接return
        }
    }
    // 判断投入钱币是否为4种面额之中的一种
    if (cnt != 1 && cnt != 2 && cnt != 5 && cnt != 10){
        cout << "E002:Denomination error" << endl;
    }else if ((cnt==5||cnt==10)&&(coins[0]+2*coins[1])<cnt){
        cout << "E003:Change is not enough, pay fail" << endl;
    }else{
        // 存钱盒中对应金额的纸币数量加1
        for (int i = 0; i < 4; ++i){
            if(cash[i] == cnt){
                coins[i]++;
                break;
            }
        }
        balance += cnt;     // 更新剩余金额
        cout << "S002:Pay success,balance=" << to_string(balance) << endl;
    }
}

// 实现找零功能
void cashOut(const string str){
    if(balance == 0){
        cout << "E009:Work failure" << endl;
        return;
    }
    int rest = balance;
    // 贪心
    vector<int> cnt(4, 0);
    for (int i = 3; i >= 0; --i){
        cnt[i] = min(coins[i], rest / cash[i]);
        coins[i] -= cnt[i];
        rest -= cnt[i] * cash[i];
    }
    // 判断当前的是否为最优方案
    if(rest!=0 && cnt[2]%2 && coins[1]*2>5){ 
        // 2的数量比较多，将5兑成2
        coins[2]++;     
        cnt[2]--;
        cnt[1] += min((rest + 5) / 2, coins[1]);
        coins[1] -= cnt[1];
    }
    balance = 0;    // 清零金额
    for (int i = 0; i < 4; ++i){
        cout << to_string(cash[i]) << " "
             << "yuan coin number=" << to_string(cnt[i]) << endl;
    }
}

// 实现查询功能
void query(const string str){
    int flag = 0, pos = 1, len = str.length();
    while(pos < len && str[pos] == ' ')
        ++pos;
    while(pos < len && str[pos] != ' '){
        flag *= 10;
        flag += str[pos++] - '0';
    }
    // 判断是否有空格以及参数是否合法
    if(len != 3 || flag > 1){
        cout << "E010:Parameter error" << endl;
    }else if(flag == 1){                    // 查询金额，直接输出即可
        for (int i = 0; i < 4; ++i){
            cout << to_string(cash[i]) << " yuan coin number=" 
             << to_string(coins[i]) << endl;
        }
    }else{                                  // 查询货物
        vector<int> ids(6, 0);              // 下标数组
        iota(ids.begin(), ids.end(), 1);
        sort(ids.begin(), ids.end(), [&](const int i, const int j){
            if(things[i] == things[j])      // 数量一致，按下标升序
                return i < j;
            return things[i] > things[j];   // 数量不一致，按数量降序
        });
        for (int i = 0; i < 6; ++i){
            // 注意商品编号从1开始而数组从0开始
            cout << "A" << to_string(ids[i] + 1) << " "
             << to_string(prize[ids[i]]) << " " 
             << to_string(things[ids[i]]) << endl;
        }
    }
}

// 实现购买功能
void buy(const string str){
    // 查找A在字符串的位置，后边就是商品编号
    int pos = str.find('A')+1, len = str.length();
    int idx = 0;
    // 获取商品编号
    while(pos < len && str[pos] != ' '){
        idx *= 10;
        idx += str[pos++] - '0';
    }
    // 商品编号非法
    if(idx > 6 || idx == 0){
        cout << "E006:Goods does not exist" << endl;
    }else if(things[idx-1] == 0){                   // 对应商品已卖完
        cout << "E007:The goods sold out" << endl;
    }else if(balance < prize[idx-1]){               // 剩余金额不足支付
        cout << "E008:Lack of balance" << endl;
    }else{                                          // 购买成功
        things[idx - 1]--;                          // 数量-1
        balance -= prize[idx - 1];                  // 更新剩余金额
        cout << "S003:Buy success,balance=" 
         << to_string(balance) << endl;
    }
}

// 调用以上功能
void handler(const string str){
    char ch = str[0];
    if(ch == 'r'){
        systemInit(str);
    }else if(ch == 'p'){
        cashIn(str);
    }else if(ch == 'b'){
        buy(str);
    }else if(ch == 'c'){
        cashOut(str);
    }else if(ch == 'q'){
        query(str);
    }
}

int main(void){
    string str;
    while(getline(cin, str)){
        memset(coins, 0, sizeof(coins));        // 初始化存钱盒
        memset(things, 0, sizeof(things));      // 初始化物品
        balance = 0;                            // 初始化剩余金额
        int l = 0, len = str.length();
        while(l < len){
            // 截取命令行，分成若干个命令
            int r = find(str.begin()+l, str.end(), ';') - str.begin();
            string operate = str.substr(l, r - l);
            l = r + 1;
            //cout << operate << endl;
            handler(operate);                   // 执行命令
        }
    }
}