首页 > 其他分享 >零钱兑换问题——三种题解方法

零钱兑换问题——三种题解方法

时间:2022-12-05 16:22:44浏览次数:41  
标签:cnt int 题解 namespace break 零钱 兑换 using include

第一种:

暴力解法:
5、2、1都考虑 , 只有等于才可cnt++,小于m要continue,大于m要break

#include <iostream>
using namespace std;

int main()
{
    int m,cnt=0;
    cin>>m;
    
    for(int i=0;i<=m/5;i++){
        
        for(int j=0;j<=m/2;j++){
            
            if(i*5+j*2>m)
                break;
            for(int k=0;k<=m;k++){ //小于m的话继续进行此循环即可
                
                if(i*5+j*2+k==m)
                    cnt++;
                else if(i*5+j*2+k>m)
                    break;
            }
        }
    }
    cout<<cnt;
    
    return 0;
}

第二种:

只考虑5、2,若小于m则剩下的全换成1(所以小于等于m都可以cnt++)

#include <iostream>
using namespace std;

int main()
{
    int m,cnt=0;
    cin>>m;
    
    for(int i=0;i<=m/5;i++){
        for(int j=0;j<=m/2;j++){
            if(i*5+j*2>m)
                break;
            else //小于的话全换成1是一种情况,等于的话也是一种情况
                cnt++;
        }
    }
    
    cout<<cnt;
    
    return 0;
}

第三种:

只考虑5,剩下换为2和1

#include <iostream>
using namespace std;

int main()
{
    int m,cnt=0;
    cin>>m;
    
	//核心!!
	/*5是0到m/5的值,m中去除掉5的个数*5,剩下的全换为2和1
	(m-5*i)/2 即有几个2,有几个2即有几个2可以换为两个1,即有几个方法
	+1 即全是2,不换,是一种方法*/
    for(int i=0;i<=m/5;i++){
        cnt=cnt+(m-5*i)/2+1;
    }
    
    cout<<cnt;
    
    return 0;
}

标签:cnt,int,题解,namespace,break,零钱,兑换,using,include
From: https://www.cnblogs.com/kathryn921/p/16952616.html

相关文章

  • 题解 [AGC047C] Product Modulo
    显然不能暴力算两两的乘积,而积取模而结果不取模提示我们模数肯定有用。所有为\(0\)的\(a_i\)对答案不会产生任何贡献,可以直接删除,下文不再考虑这种情况。同时我们约定......
  • 能力提升——搜索 题解
    BP5194[USACO05DEC]ScalesS在洛谷,享受coding的快乐AC历程:0pts(MLE)60pts(6AC+4TLE)100pts(AC)虽然题目中说n≤1000,但考虑到“每个砝码的质量至少等于前面两个......
  • JOISC 2022 简要题解
    版刷JOISC的计划就这么结束了。鸽了许多题,懵懵懂懂过来的,兴奋的开始,中途得知省选没了,又鸽了一段时间。好歹是完结了,撒花撒花。总体上题目质量很高,很开心以及荣幸有机会......
  • 题解 [ARC121D] 1 or 2
    诈骗题,竟然评到了\(2784\)的惊人高分(快到红了),来补个题解。题意:有两个可重集\(A,B\),\(B\)初始为\(\varnothing\)。每次从\(A\)中删除一个或两个数,并将它们的和加入......
  • 无知时诋毁原神——题解
    P8880无知时诋毁原神题意简述:给定一个\(0\simn-1\)的排列\(c\)。构造两个同样为\(0\simn-1\)的排列的\(a,b\),满足\(\foralli\in[1,n],c_i=(a_i+b_i)\bmodn\)。如......
  • sql题解--打折日期交叉问题
    题目-打折日期交叉问题现有各品牌优惠周期表(promotion_info)如下,其记录了每个品牌的每个优惠活动的周期,其中同一品牌的不同优惠活动的周期可能会有交叉。promotion_id......
  • win11系统vmware虚拟机报错“不支持嵌套虚拟化”问题解决方案汇总
    一、报错内容vmware0虚拟机中开启虚拟化主机时,报错“Error:Failureinvalidatingvirtualizationcapabilities”[root@localhost~]#rht-vmctlfullresetclassroom......
  • 微信支付 “商家转账到零钱”
    ​这里有个坑1:转账低于5毛会失败2:转账金额需要自己取整一下,微信官方金额是分为单位,换算成元时可能会除不尽{"code":"PARAM_ERROR","detail":{......
  • NOIP2022 T1 种花 题解
    Part1吐槽&退役寄考场上唯一AC的题目,T3看错题以为可以删去不止1条边,T4输出没换行,寄。最后喜提100+0+0+0,给我的OI生涯画上了一个不完美的句号。Part2题解题目让统计......
  • CF1709 题解
    比赛链接:https://codeforces.com/contest/1709题解:AB水题//bySkyRainWind#include<cstdio>#include<vector>#include<cassert>#include<cstring>#include<......