题意

如果你在考试遇到这种题,那我只能祝你好运.

2,3,4,5,8,6 单价商品

1,2,5,10 面值钱币

状态:

商品: 购买减1

钱盒: 1. 投币增加 2. 退币减少

投币余额: 1. 投币则增加 2. 购买则减少 3. 初始化/退币清空

操作:

初始化: 1. 商品 2. 钱盒 3. 投币余额清零

投币: 只允许 1,2,5,10

退币: 1. 总张数最少原则 2. 零钱不足,让用户损失最少的方案退 3. 投币余额清零

购买: 1.商品减1 2. 投币余额减商品价格

查询: 输出内容不改变状态

数据有点问题

对于 查询 操作 全部输出错误即可

方法

实现

虽然题面很长,但是实际上把题目逐字句翻译成代码即可, 接近 100行即可实现.

唯一无法直接翻译的就是退币逻辑

1. 要用户尽量少损失
2. 最少数量钱币

以题目中的样例例如：假设存钱盒内只有4张2元，无其它面额钱币。如果需要退币7元，系统因零钱不足无法退币，则继续尝试退币6元，最终系统成功退币3张2元,用户损失1元钱币。为例

在实现尽量少损失的时候采取,枚举法

由此,金额7是不可行的,尝试金额减1

因此金额6是可行的

代码

#include<bits/stdc++.h>
using namespace std;
int a[10]; // 商品 2 3 4 5 8 6
int cost[] = {0,2,3,4,5,8,6};
int m[11]; // 钱盒 1 2 5 10
int y[] = {1,2,5,10}; // 面值

// 检查 balance是否可以由 m[11] 构成
bool ok(int balance,int idx = 10){
    if(idx == 0)return balance == 0;
    if(balance == 0)return true;
    for(int i = 0 ;i <= m[idx]; i++){
        if(balance < i*idx) break;
        bool r = ok(balance - i*idx,idx-1);
        if(r)return r;
    }
    return false;
}

// 执行退还操作
bool cit(int balance){
    int c[] = {0,0,0,0}; // 个数
    for(int i = 3;i>=0;i--){
        c[i] = min(balance/y[i],m[y[i]]);
        m[y[i]] -= c[i];
        balance -= c[i] * y[i];
    }
    for(int i = 0 ;i < 4;i++){
        printf("%d yuan coin number=%d\n",y[i],c[i]);
    }
    return false;
}

int main(){
    int balance = 0; // 投币余额
    char op;
    while(~scanf("%c",&op)){
        if(op == 'r'){ // 初始化
            scanf("%d-%d-%d-%d-%d-%d %d-%d-%d-%d;",a+1,a+2,a+3,a+4,a+5,a+6,m+1,m+2,m+5,m+10);
            balance = 0;
            printf("S001:Initialization is successful\n"); // 初始化成功
        }else if(op == 'p'){ // 投币
            int v;
            scanf("%d;",&v);
            if(!(v==1 || v==2 || v==5 ||v==10)){ // 如果投入非1元、2元、5元、10元的钱币面额
                printf("E002:Denomination error\n");
            }else if(!(v==1 || v==2) && m[1]+2*m[2] < v){ // 如果存钱盒中1元和2元面额钱币总额小于本次投入的钱币面额
                printf("E003:Change is not enough, pay fail\n");
            }else if(a[1]+a[2]+a[3]+a[4]+a[5]+a[6] == 0){ // 如果自动售货机中商品全部销售完毕，投币失败。
                printf("E005:All the goods sold out\n");
            }else{
                m[v]++; // 钱盒+1
                printf("S002:Pay success,balance=%d\n", balance+=v);
            }
        }else if(op == 'b'){ // 购买
            char A;
            int idx;
            scanf(" %c%d;",&A,&idx);
            if(A != 'A' || idx < 1 || idx > 6){// 如果购买的商品不在商品列表中
                printf("E006:Goods does not exist\n");
            }else if(a[idx] == 0){ // 如果所购买的商品的数量为0
                printf("E007:The goods sold out\n");
            }else if(balance < cost[idx]){ // 如果投币余额小于待购买商品价格
                printf("E008:Lack of balance\n");
            }else{ // 购买成功
                a[idx]--; // 商品-1
                printf("S003:Buy success,balance=%d\n", balance-=cost[idx]);
            }
        }else if(op == 'c'){ // 退币
            if(balance == 0){ // 如果投币余额等于0的情况下
                printf("E009:Work failure\n");
            }else{
                while(!ok(balance))balance--; // 最小损失
                cit(balance);
                balance = 0;
            }
        }else if(op == 'q'){
            int t;
            scanf("%d;",&t);
            printf("E010:Parameter error\n"); // 应该是牛客数据全部有误 直接输出失败
            continue;
            if(t == 0){ // 查询商品信息
                for(int i = 1 ;i <= 6;i++){
                    printf("A%d %d %d\n",i,cost[i],a[i]);
                }
            }else if(t == 1){ // 查询存钱盒信息
                for(int i = 0 ;i < 4;i++){
                    printf("%d yuan coin number=%d\n",y[i],m[y[i]]);
                }
            }else{ // 如果“查询类别”参数错误
                printf("E010:Parameter error\n");
            }
        }
    }
    
    return 0;
}

复杂度分析

时间复杂度: 全部是读一句处理一句,所以时间复杂度为$O(n)O(n)$

空间复杂度: 主要是常数个数的变量存储,所以 空间复杂度为$O(1)O(1)$

贪心退还规则

在退还上,可以直接从大到小采取贪心,而不用检查一次可行性再分配一次. 因此可以直接退还

代码

#include<bits/stdc++.h>
using namespace std;
int a[10]; // 商品 2 3 4 5 8 6
int cost[] = {0,2,3,4,5,8,6};
int m[11]; // 钱盒 1 2 5 10
int y[] = {1,2,5,10}; // 面值

// 执行退还操作
bool cit(int balance){
    int c[] = {0,0,0,0}; // 个数
    for(int i = 3;i>=0;i--){
        c[i] = min(balance/y[i],m[y[i]]); // 不大于个数 不大于投币总额
        m[y[i]] -= c[i];
        balance -= c[i] * y[i];
    }
    for(int i = 0 ;i < 4;i++){
        printf("%d yuan coin number=%d\n",y[i],c[i]);
    }
    return false;
}

int main(){
    int balance = 0; // 投币余额
    char op;
    while(~scanf("%c",&op)){
        if(op == 'r'){ // 初始化
            scanf("%d-%d-%d-%d-%d-%d %d-%d-%d-%d;",a+1,a+2,a+3,a+4,a+5,a+6,m+1,m+2,m+5,m+10);
            balance = 0;
            printf("S001:Initialization is successful\n"); // 初始化成功
        }else if(op == 'p'){ // 投币
            int v;
            scanf("%d;",&v);
            if(!(v==1 || v==2 || v==5 ||v==10)){ // 如果投入非1元、2元、5元、10元的钱币面额
                printf("E002:Denomination error\n");
            }else if(!(v==1 || v==2) && m[1]+2*m[2] < v){ // 如果存钱盒中1元和2元面额钱币总额小于本次投入的钱币面额
                printf("E003:Change is not enough, pay fail\n");
            }else if(a[1]+a[2]+a[3]+a[4]+a[5]+a[6] == 0){ // 如果自动售货机中商品全部销售完毕，投币失败。
                printf("E005:All the goods sold out\n");
            }else{
                m[v]++; // 钱盒+1
                printf("S002:Pay success,balance=%d\n", balance+=v);
            }
        }else if(op == 'b'){ // 购买
            char A;
            int idx;
            scanf(" %c%d;",&A,&idx);
            if(A != 'A' || idx < 1 || idx > 6){// 如果购买的商品不在商品列表中
                printf("E006:Goods does not exist\n");
            }else if(a[idx] == 0){ // 如果所购买的商品的数量为0
                printf("E007:The goods sold out\n");
            }else if(balance < cost[idx]){ // 如果投币余额小于待购买商品价格
                printf("E008:Lack of balance\n");
            }else{ // 购买成功
                a[idx]--; // 商品-1
                printf("S003:Buy success,balance=%d\n", balance-=cost[idx]);
            }
        }else if(op == 'c'){ // 退币
            if(balance == 0){ // 如果投币余额等于0的情况下
                printf("E009:Work failure\n");
            }else{
                cit(balance); // 最小损失
                balance = 0;
            }
        }else if(op == 'q'){
            int t;
            scanf("%d;",&t);
            printf("E010:Parameter error\n");
            continue;
            if(t == 0){ // 查询商品信息
                for(int i = 1 ;i <= 6;i++){
                    printf("A%d %d %d\n",i,cost[i],a[i]);
                }
            }else if(t == 1){ // 查询存钱盒信息
                for(int i = 0 ;i < 4;i++){
                    printf("%d yuan coin number=%d\n",y[i],m[y[i]]);
                }
            }else{ // 如果“查询类别”参数错误
                printf("E010:Parameter error\n");
            }
        }
    }
    
    return 0;
}

复杂度分析

时间复杂度: 全部是读一句处理一句,所以时间复杂度为$O(n)O(n)$

空间复杂度: 主要是常数个数的变量存储,所以 空间复杂度为$O(1)O(1)$