首页 > 试题广场 >

日本旅行

[编程题]日本旅行

热度指数：1168 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 64M，其他语言128M
算法知识视频讲解

楚乔、宇文玥和燕洵在日本旅行，经过了几天的游玩之后，钱包里出现了大量硬币，楚乔决定用钱包里的硬币为宇文玥和燕洵在自动贩卖机买水。楚乔的钱包里有1元、5元、10元、50元、100元和500元硬币各C1,C5,C10,C50,C100,C500枚。现在要用这些硬币来到自动贩卖机买价格为A的饮料，假设自动贩卖机所需的硬币金额必须是刚刚好，不能多也不能少，最少需要多少枚硬币？

限制条件

0≤ C1,C5,C10,C50,C100,C500≤1000000000

0≤A≤1000000000

依次输入C1,C5,C10,C50,C100,C500和A，以空格分隔，输出最少所需硬币数，如果该金额不能由所给硬币凑出，则返回NOWAY

输入描述:

依次输入C1,C5,C10,C50,C100,C500和A，以空格分隔

输出描述:

输出最少所需硬币数，如果该金额不能由所给硬币凑出，则返回NOWAY

示例1

输入

3 2 1 3 0 2 620

输出

算法知识视频讲解

Python

白色纯度

python3

写代码力求简单通俗易懂，其次是时间和空间的优化。今天被华为秋招题目虐了，已经自闭了！尤其那个全组合，真的是气死我了！

def solve(c,num,money):
    res = 0
    for i in range(len(num)-1,-1,-1):
        while money>=num[i] and c[i]>0:
            money -= num[i]
            c[i] -= 1
            res += 1
    return res
if __name__=='__main__':
    c = list(map(int,input().split()))
    money = c[-1]
    num = [1,5,10,50,100,500]
    ans = solve(c[:-1],num,money)
    if ans==0:
        print('NOWAY')
    else:
        print(ans)

发表于 2019-09-07 23:46:18 回复(0)

Python

lx的流星

while True:
    try:
        C1,C5,C10,C50,C100,C500,A=map(int,input().split(' '))
        #print(C1,C5,C10,C50,C100,C500,A)
        list1=[500,100,50,10,5,1]
        list2=[C500,C100,C50,C10,C5,C1]
        for i in range(6):#将硬币数为0的硬币值归0
            if list2[i]==0:
                list1[i]=0
        num=0
        while A>0 and len(list2)!=0:
            #print(A)
            max_num=list1[0]
            if max_num!=0:
                if A>=max_num:
                    num1=A//max_num
                    if num1<=list2[0]:
                        num+=num1
                        A-=max_num*num1
                        list1.pop(0)
                        list2.pop(0)
                    else:
                        num+=list2[0]
                        A-=max_num*list2[0]
                        list1.pop(0)
                        list2.pop(0)
                else:
                    list1.pop(0)
                    list2.pop(0)     
            else:
                list1.pop(0)
                list2.pop(0)
        if A==0:
            print(num)
        else:
            print('NOWAY')
    except:
        break

编辑于 2019-07-26 14:02:55 回复(0)