题意：
实现自动售货功能（自己看题）。
方法一：
模拟
思路：这道题题目描述较长，我这里简单概括一下。
1、顾客一次只能投一个币，购买一个商品；
2、售货机有不同商品的单价和数量，售货机的存钱盒有1,2,5,10四种面额的钱币数量；
3、顾客只能投1,2,5,10四种面额的钱币，并且投入的钱币会累加到一个临时变量（即投币余额）；4、顾客可以指定售货机中的一个商品进行购买；5、顾客可以根据 ”退币原则” 进行退币操作，“退币原则”的意思是当售货机没有零钱找个顾客，会尽可能减少用户损失，涉及贪心；6、顾客可以查看商品信息和存钱盒的信息，涉及排序。
#include <bits/stdc++.h>
using namespace std;
int a[10]={0};//数量
int b[6]={2,3,4,5,8,6};//商品单价
string c[6]={"A1","A2","A3","A4","A5"};
unordered_map<int,int> mp;//下标映射钱币面额
struct node{//排序的结构体
string name;
int price;
int cnt;
bool operator<(const node &x)const{
return cnt>x.cnt;
}
}d[6];
int main(){
mp[6]=1;//初始化
mp[7]=2;
mp[8]=5;
mp[9]=10;
string s;
while(getline(cin,s)){//输入
int len=s.size();
string x="";
int balance=0;
for(int i=0;i<len;i++){
if(s[i]==';'){
if(x[0]=='r'){
//初始化
int k=0;
int num=0;
x+='-';
for(int j=2;j<x.size();j++){
if(x[j]==' ')
x[j]='-';
if(x[j]=='-'){
a[k++]=num;
num=0;
}else{
num=num*10+x[j]-'0';
}
}
a[k++]=num;
cout << "S001:Initialization is successful" << endl;
}else if(x[0]=='c'){//退币
if(balance==0){
cout << "E009:Work failure\n";
}else{
stack<int> st;
for(int j=9;j>=6;j--){//贪心
int num=0;
while(a[j]>0&&balance>=mp[j]){
balance-=mp[j];
a[j]--;
num++;
}
st.push(num);
}
int j=6;
while(j<=9&&!st.empty()){
cout << mp[j] << " yuan coin number=" << st.top() << endl;
j++;
st.pop();
}
}
balance=0;//余额赋值为0
}else if(x[0]=='q'){//查询
if(x[1]!=' '){
cout << "E010:Parameter error\n";
}else if(x[1]=='0'){
for(int j=0;j<=5;j++){
d[i]={c[j],b[j],a[j]};
}
stable_sort(d,d+6);//稳定排序
for(int j=0;j<=5;j++){//输出商品的信息
cout << d[j].name << " " << d[j].price << " " << d[j].cnt << endl;
}
}else if(x[1]=='1'){//输出存钱盒的信息
for(int j=6;j<=9;j++){
cout << mp[j] << " yuan coin number=" << a[j] << endl;
}
}
}else if(x[0]=='p'){//投币
int num=0;
for(int j=2;j<x.size();j++){
num=num*10+x[j]-'0';
}
if(num!=1&&num!=2&&num!=5&&num!=10){//钱币面额不符合
cout << "E002:Denomination error\n";
}else if(a[6]+a[7]*2<num&&num!=1&&num!=2){//存钱盒中1元和2元面额钱币总额小于本次投入的钱币面额
cout << "E003:Change is not enough, pay fail\n";
}else if(a[0]+a[1]+a[2]+a[3]+a[4]+a[5]==0){//自动售货机中商品全部销售完毕
cout << "E005:All the goods sold out\n";
}else{
for(auto y:mp){//通过钱币面额找到对应钱币数量+1
if(y.second==num){
a[y.first]++;
break;
}
}
balance+=num;//累加余额
cout << "S002:Pay success,balance=" << balance << endl;
}
}else if(x[0]=='b'){//购买商品
int y=x[3]-'0'-1;
if(balance<b[y]){
cout << "E008:Lack of balance\n";
}else{
balance-=b[y];
a[y]--;
cout << "S003:Buy success,balance=" << balance << endl;
}
}
x="";
}else{
x+=s[i];
}
}
}
return 0;
}
时间复杂度：%2C%E9%81%8D%E5%8E%86%E5%AD%97%E7%AC%A6%E4%B8%B2%E3%80%82)
空间复杂度：%2C%E5%95%86%E5%93%81%E7%A7%8D%E7%B1%BB%E5%92%8C%E9%92%B1%E5%B8%81%E9%9D%A2%E9%A2%9D%E4%B8%AA%E6%95%B0%E5%88%86%E5%88%AB%E6%98%AF6%2C4%EF%BC%8C%E5%9B%A0%E6%AD%A4%E5%B8%B8%E6%95%B0%E7%BA%A7%E5%88%AB%E5%AD%98%E5%82%A8%E7%A9%BA%E9%97%B4%E3%80%82)
方法二：
java
思路：java 实现
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
class Node{//排序的结构体
String name;
int price;
int cnt;
public Node(String name, int price, int cnt) {
this.name = name;
this.price = price;
this.cnt = cnt;
}
}
class MyComparator implements Comparator<Node>{//实现比较器
@Override
public int compare(Node o1, Node o2) {
if(o1.cnt<o2.cnt){//数量降序
return 1;
}else{
if(o1.name.compareTo(o2.name)>0){
return 1;
}
}
return 0;
}
}
public class Main {
static int[] a={0,0,0,0,0,0,0,0,0,0};//数量
static int[] b={2,3,4,5,8,6};//商品单价
static String[] c={"A1","A2","A3","A4","A5"};
static HashMap<Integer,Integer> mp=new HashMap<>();//下标映射钱币面额
static ArrayList<Node> d=new ArrayList<>();
public static void main(String[] args) throws IOException {
for (int i = 0; i <=5 ; i++) {
d.add(new Node("",0,0));
}
//初始化
mp.put(6,1);
mp.put(7,2);
mp.put(8,5);
mp.put(9,10);
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String s;
while((s=br.readLine())!=null){//输入
int len=s.length();
String x="";
int balance=0;
for(int i=0;i<len;i++){
if(s.charAt(i)==';'){
if(x.charAt(0)=='r'){
//初始化
int k=0;
int num=0;
x+='-';
for(int j=2;j<x.length();j++){
if(x.charAt(j)=='-'||x.charAt(j)==' '){
a[k++]=num;
num=0;
}else{
num=num*10+x.charAt(j)-'0';
}
}
System.out.println("S001:Initialization is successful");
}else if(x.charAt(0)=='c'){//退币
if(balance==0){
System.out.println("E009:Work failure");
}else{
// for(int j=6;j<=9;j++){
// System.out.print(a[j]+" ");
// }
// System.out.println();
Stack<Integer> st=new Stack<>();
for(int j=9;j>=6;j--){//贪心
int num=0;
while(a[j]>0&&balance>=mp.get(j)){
balance-=mp.get(j);
a[j]--;
num++;
}
st.add(num);
}
int j=6;
while(j<=9&&!st.empty()){
System.out.println(mp.get(j)+" yuan coin number="+st.peek());
j++;
st.pop();
}
}
balance=0;//余额赋值为0
}else if(x.charAt(0)=='q'){//查询
if(x.charAt(1)!=' '){
System.out.println("E010:Parameter error");
}else if(x.charAt(1)=='0'){
for(int j=0;j<=5;j++){
d.get(j).name=c[j];
d.get(j).price=b[j];
d.get(j).cnt=a[j];
}
//稳定排序
d.sort(new MyComparator());
for(int j=0;j<=5;j++){//输出商品的信息
System.out.println(d.get(j).name+" "+d.get(j).price+" "+d.get(j).cnt);
}
}else if(x.charAt(1)=='1'){//输出存钱盒的信息
for(int j=6;j<=9;j++){
System.out.println(mp.get(j)+" yuan coin number="+a[j]);
}
}
}else if(x.charAt(0)=='p'){//投币
int num=0;
for(int j=2;j<x.length();j++){
num=num*10+x.charAt(j)-'0';
}
if(num!=1&&num!=2&&num!=5&&num!=10){//钱币面额不符合
System.out.println("E002:Denomination error");
}else if(a[6]+a[7]*2<num&&num!=1&&num!=2){//存钱盒中1元和2元面额钱币总额小于本次投入的钱币面额
System.out.println("E003:Change is not enough, pay fail");
}else if(a[0]+a[1]+a[2]+a[3]+a[4]+a[5]==0){//自动售货机中商品全部销售完毕
System.out.println("E005:All the goods sold out");
}else{
for(Map.Entry<Integer,Integer> entry:mp.entrySet()){//通过钱币面额找到对应钱币数量+1
if(entry.getValue()==num){
a[entry.getKey()]++;
break;
}
}
balance+=num;//累加余额
System.out.println("S002:Pay success,balance="+balance);
}
}else if(x.charAt(0)=='b'){//购买商品
int y=x.charAt(3)-'0'-1;
if(balance<b[y]){
System.out.println("E008:Lack of balance");
}else{
balance-=b[y];
a[y]--;
System.out.println("S003:Buy success,balance="+balance);
}
}
x="";
}else{
x+=s.charAt(i);
}
}
}
}
}
时间复杂度：空间复杂度：
京公网安备 11010502036488号