题解 | #自动售货系统#

我看大家用的退钱的方法都是贪心,

但是如果这样的情况呢?

如1, 2, 5, 10的个数分别是 0, 3, 1, 1

需要退钱 6 元 那么只能返回5块钱1个

但是正确答案应该是2+2+2吧?

是测试案例没有覆盖到? 还

是优先度 张数最少 > 正确匹配?

#include <bits/types/mbstate_t.h>
#include <iostream>
#include <map>
#include <vector>
using namespace std;

map<string, int> nameToInt = {
    {"A1", 0},
    {"A2", 1},
    {"A3", 2},
    {"A4", 3},
    {"A5", 4},
    {"A6", 5}
};

class Good {
  public:
    string name;
    int price;
    int num = 0;

    Good(string name, int price, int num) {
        this->name = name;
        this->price = price;
        this->num = num;
    }

    void buyOne() {
        this->num -= 1;
    }
    // void setNum(int num) {
    //     this->num = num;
    // }
};

class MoneyBox {
  public:
    int num10, num5, num2, num1;

    MoneyBox(int num1, int num2, int num5, int num10) {
        this->num1 = num1;
        this->num2 = num2;
        this->num5 = num5;
        this->num10 = num10;
    }
};

vector<string> split(string sentence, char target = ' ') {
    vector<string> ans;
    int left = 0;
    // int right = 1;
    int now = 0;
    while (now < sentence.size()) {
        if (sentence.at(now) == target) {
            // cout << left << ' ' << now << endl;
            ans.push_back(sentence.substr(left, now - left));
            left = now + 1;
            now = left;
            continue;
        }
        now++;
    }
    // cout << left << ' ' << now << endl;
    ans.push_back(sentence.substr(left, now - left));
    return ans;
}

vector<Good> inithialGood(string nums) {
    vector<string> num_list = split(nums, '-');

    // for(auto num : num_list){
    //     cout << num << endl;
    // }

    Good A1 = Good("A1", 2, stoi(num_list[0]));
    Good A2 = Good("A2", 3, stoi(num_list[1]));
    Good A3 = Good("A3", 4, stoi(num_list[2]));
    Good A4 = Good("A4", 5, stoi(num_list[3]));
    Good A5 = Good("A5", 8, stoi(num_list[4]));
    Good A6 = Good("A6", 6, stoi(num_list[5]));

    vector<Good> goods;
    goods.push_back(A1);
    goods.push_back(A2);
    goods.push_back(A3);
    goods.push_back(A4);
    goods.push_back(A5);
    goods.push_back(A6);

    return goods;
}

MoneyBox initialMoneyBox(string money) {
    vector<string> moneys = split(money, '-');
    MoneyBox moneybox = MoneyBox(stoi(moneys[0]), stoi(moneys[1]), stoi(moneys[2]),
                                 stoi(moneys[3]));

    return moneybox;
}

map<int, int> returnMoney(int money_int_left, MoneyBox& moneybox) {
    map<int, int> change = {
        {1, 0},
        {2, 0},
        {5, 0},
        {10, 0}
    };

    while (money_int_left >= 10) {
        if (moneybox.num10 > 0) {
            money_int_left -= 10;
            change.at(10) += 1;
            moneybox.num10 -= 1;
        } else {
            break;
        }
    }
    while (money_int_left >= 5) {
        if (moneybox.num5 > 0) {
            money_int_left -= 5;
            change.at(5) += 1;
            moneybox.num5 -= 1;
        } else {
            break;
        }
    }
    while (money_int_left >= 2) {
        if (moneybox.num2 > 0) {
            money_int_left -= 2;
            change.at(2) += 1;
            moneybox.num2 -= 1;
        } else {
            break;
        }
    }
    while (money_int_left >= 1) {
        if (moneybox.num10 > 0) {
            money_int_left -= 1;
            change.at(1) += 1;
            moneybox.num1 -= 1;
        } else {
            break;
        }
    }

    return change;
}

void execution(vector<string> cmd_list) {
    vector<Good> goods;
    MoneyBox moneybox = MoneyBox(0, 0, 0, 0);
    int money_int_left = 0;

    for (string cmd : cmd_list) {
        vector<string> cmds = split(cmd);

        // cout << cmds[0] << endl;
        if (cmds[0] == "r") {
            goods = inithialGood(cmds[1]);

            moneybox = initialMoneyBox(cmds[2]);

            cout << "S001:Initialization is successful" << endl;
            // cout << moneybox.num1 << " " << moneybox.num2 << " " << moneybox.num5 << " " <<
            //      moneybox.num10 << endl;
            // cout << goods[0].name << " " << goods[0].price << " " << goods[0].num << endl;


        } else if (cmds[0] == "p") {
            int money_int = stoi(cmds[1]);

            if (money_int != 1 && money_int != 2 && money_int != 5 && money_int != 10) {
                cout << "E002:Denomination error"  << endl;
                continue;
            } else if (moneybox.num1 + moneybox.num2 * 2 < money_int) {
                if (money_int == 5 || money_int == 10) {
                    cout << "E003:Change is not enough, pay fail" << endl;
                    continue;
                }
            } else if (goods[0].num + goods[1].num + goods[2].num +
                       goods[3].num + goods[4].num + goods[5].num
                       == 0) {
                cout << "E005:All the goods sold out" << endl;
                continue;
            } else {
                money_int_left += money_int;
                if(money_int == 10){
                    moneybox.num10 += 1;
                }else if(money_int == 5){
                    moneybox.num5 += 1;
                }else if(money_int == 2){
                    moneybox.num2 += 1;
                }else if(money_int == 1){
                    moneybox.num1 += 1;
                }
                cout << "S002:Pay success,balance=" << money_int_left << endl;
            }
        } else if (cmds[0] == "b") {
            string good_name = cmds[1];

            // if(good_name != "A1" && good_name != "A2" && good_name != "A3" &&
            //     good_name != "A4" && good_name != "A5" && good_name != "A6"){
            if (nameToInt.find(good_name) == nameToInt.end()) {
                cout << "E006:Goods does not exist" << endl;
                continue;
            } else if (goods.at(nameToInt.at(good_name)).num == 0) {
                cout << "E007:The goods sold out" << endl;
                continue;
            } else if (money_int_left < goods.at(nameToInt.at(good_name)).price) {
                cout << "E008:Lack of balance" << endl;
                continue;
            } else {
                money_int_left -= goods.at(nameToInt.at(good_name)).price;
                goods.at(nameToInt.at(good_name)).buyOne();
                cout << "S003:Buy success,balance=" << money_int_left << endl;
            }
        } else if (cmds[0] == "c") {
            if (money_int_left == 0) {
                cout << "E009:Work failure" << endl;
                continue;
            } else {
                map<int, int> change = returnMoney(money_int_left, moneybox);
                cout << "1 yuan coin number=" << change.at(1) << endl;
                cout << "2 yuan coin number=" << change.at(2) << endl;
                cout << "5 yuan coin number=" << change.at(5) << endl;
                cout << "10 yuan coin number=" << change.at(10) << endl;
                money_int_left = 0;
            }
        } else if (cmds[0] == "q") {
            if (cmds[1] == "0"){
                for(int i = 0; i < 6; i++){
                    cout << goods.at(i).name << " " << goods.at(i).price << " " << goods.at(i).num << endl;
                }
            } else if(cmds[1] == "1"){
                cout << "1 yuan coin number=" << moneybox.num1 << endl;
                cout << "2 yuan coin number=" << moneybox.num2 << endl;
                cout << "5 yuan coin number=" << moneybox.num5 << endl;
                cout << "10 yuan coin number=" << moneybox.num10 << endl;
            } 
        }else if(cmds[0] == ""){
                continue;
        }else{
            cout << "E010:Parameter error" << endl;
        }
    }
}

int main() {
    string sentence;
    getline(cin, sentence);
    vector<string> cmd_list;
    cmd_list = split(sentence, ';');
    // for(auto cmd : cmd_list){
    //     cout << cmd << endl;
    // }
    execution(cmd_list);

}
// 64 位输出请用 printf("%lld")