问题标题: 酷町堂：1418 超市结账

Question

0

已解决

毕小曼

初级光能

http://judge.codingtang.com/problem/1418/

1418 超市结账

题目描述 Description

顾客在超市购买物品后都会在收银台结账，假设超市收银台有若干张面额为1元、2元、5元、10元、20元、50元和100元的纸币，相应的售货员会找顾客些零钱，如何使找零钱所用纸币张数最小？（假设顾客购买物品价格都为整数）例如顾客购买物品价格为63元，顾客给收银员70元，收银员需要找给顾客7元。而7元可用一张5元和一张2元，共2张纸币，也可以用三张2元和一张1元，共4张纸币，那么7元零钱用一张5元和一张2元所用纸币张数最小。

输入描述 Input Description

输入为一行，有2个整数(输入的整数小于100000)，用空格隔开，分别表示顾客购买物品的价格和顾客给收银员的钱。

输出描述 Output Description

输出为若干行，第一行到倒数第二行分别表示不同面额纸币及其张数，最后一行表示收银员找零钱所用最少纸币张数。

样例输入 Sample Input

63 70

样例输出 Sample Output

5:1
2:1
2

怎么写？

不会不会！

Please help me,thank you!

酷町豆刷题求解 C++ 0条评论 5 年，9 月前

Answer 1

已采纳

王浩然

新手光能

方法1:7个if从大到小直接判断，看多少元可以弄多少张，原因是只要钱的面值越大，所需的张数就越小。

模板（注：m为a,b的差值）

if(m>=100)
    {
        sum[1]+=m/100;
        m-=sum[1]*100;
        t+=sum[1];
        cout<<100<<":"<<sum[1]<<endl;
    }

方法2：使用while一次一次加，模板只需稍微改改

Answer 2

钱帅文

中级天翼

1

Answer 3

刘陶哲

修练者

推荐方案：贪心

核心：让每次取出的钞票尽可能大

核心代码：

    while(i!=0)
    {
        if(sum-a[i]>0)
        {
            sum-=a[i];
            b[i]++;
            c++;
        }
        else if(sum-a[i]==0)
             {
                b[i]++;
                i=0;
                c++;
             }
        else i--;
    }

注释：

a[i]是指第i小的钞票;代码:int a[8]={0,1,2,5,10,20,50,100};

b[i]是指第i小的钞票的数量;

i在循环之前要赋值为7；

c是指钞票的总张数

问题标题: 酷町堂：1418 超市结账

3 个回答: