标签搜索

目 录CONTENT

文章目录

小Q购物.md

小小城
2021-08-22 / 0 评论 / 0 点赞 / 3 阅读 / 2,047 字 / 正在检测是否收录...
温馨提示:
本文最后更新于 2022-05-02,若内容或图片失效,请留言反馈。部分素材来自网络,若不小心影响到您的利益,请联系我们删除。

小Q购物

@[toc]

一、题目描述

小Q去商场购物,经常会遇到找零的问题。

小Q现在手上有n种不同面值的硬币,每种面值的硬币都有无限多个。

为了方便购物,小Q希望带尽量少的硬币,并且要能组合出1到m之间(包含1和m)的所有面值

输入格式

第一行包含两个整数m和n。

接下来n行,每行一个整数,第 i+1 行的整数表示第 i 种硬币的面值。

输出格式

输出一个整数,表示最少需要携带的硬币数量。

如果无解,则输出-1。

数据范围

1≤n≤100 1≤m≤109 1≤硬币面值≤109

输入样例:

20 4
1
2
5
10

输出样例:

5

二、题目分析

题意:给你n种硬币让你用最少的硬币凑出1到m之间的所有金额

  •  这道题采用分段的思想:然后我们可以分段计算,先计算 凑出[1,a1-1]至少需要多少硬币,再计算[1,a2-1],.....算到[1,m]
  •  计算[1,ai-1]的时候,那么我们只能用前i-1种硬币来凑,为了使用硬币最少,使用a[i-1]这个面值的硬币来凑。
  •  首先对给出的硬币金额进行排序,方便找更大金额的硬币
sort(a,a + n);
  •  第二步判断最小的硬币金额是否大于1,如果大于1,那么直接返回-1。
if(a[0] != 1)
{
    puts("-1");
}
  •  第三步对给出的硬币进行筛选,把金额大于m的直接给pass 掉
while(a[n-1]>m) 
	n--;
  •  第四步题意要求凑出金额为1到m,我们就把最后一个硬币的金额看作m + 1,原因在后面解释:
a[n] = m + 1;
  •  接下来就开始凑:先给一个公式:$a[i] * k + sum >= a[i + 1] - 1$(k向上取整)。公式是用来求凑出金额a[i + 1] - 1所需金额为a[i ]的硬币个数k,sum代表已经凑出的金额范围。

  •  公式解释:假设现在已经使用到硬币a[i]了,已经凑出的金额范围为sum = a[i] - 1,下一次目标是凑出金额为a[i + 1] - 1。现在可以使用的硬币金额为a[i - 1]、a[i]、a[i + 1],不能使用a[i - 1]是因为他虽然可以凑出所需的金额,但是数量太多。a[i + 1]会存在因为面值太大而跳过某个面值的可能,所以使用a[i]。我们需要使用k个a[i]的金币加上已经凑出的金额范围sum大于等于目标金额a[i + 1] - 1,求去k,k就是最少的方案

  •  为什么用a[i]来凑a[i + 1] - 1,不凑到a[i + 1]?因为凑到a[i + 1]了直接可以用a[i + 1]这个金额的硬币了(保证用最少的硬币)

  •  例:假设硬币金额为1 ,2,5,10 。m的值为25.

  •  根据分析,硬币金额变为1,2,5,10,26.

  •  开始凑,对于金额1,只能用一枚面值1的硬币。套用公式就是$a[0] * k + 0 >= a[1] - 1$(一开始已经凑出的金额范围sum等于0,还没开始凑嘛)求得k等于1(向上取整).同时更新已经凑出的金额范围sum。sum += k * a[i] = 1。

  •  对于金额2,既可以用面值为1的硬币也可以用面值为2的硬币,但是为了保证用最少的硬币,所以使用面值为2的硬币,因为它所凑出的面值范围为1到3。套用公式就是a[1] * k + sum >= a[2] - 1,sum等于1,求的k等于2(向上取整),同时更新sum,sum = 5

  •  依次类推.......
    在这里插入图片描述

三、代码

#include<algorithm>
#include <iostream>
#include<cstring>
#include <cstdio>
using namespace std;
typedef long long ll;
const int maxn=2e5+10;

//分别代表硬币的数量和凑金额的范围m
int n,m;

//数组a,代表每个硬币的面值
int a[maxn];

int main()
{
    cin>>m>>n;
    for(int i = 0;i < n;i++)
    {
        cin>>a[i];
    }
    
    //排序
    sort(a,a + n);
    
    //过滤掉面值大于m的硬币
    while(a[n - 1] > m) 
    	n--;
    
    //把范围m当作一种特殊的硬币
    a[n]=m + 1;
    
    if(a[0] != 1)
    {
        puts("-1");
    }
    else
    {
    	//保存已经凑出的金额范围
        int sum=0;

		//保存所需硬币的个数
        int ans=0;

		//开始遍历每个硬币的面额,直到凑出m面值的硬币出来,注意⚠️最后一枚
		//硬币的面值是m + 1,我们只需要凑出m即可,所以不会用到m + 1
        for(int i=0;i<n;i++)
        {
        	//根据公式求去所需硬币的个数k,向上取整
            int k = (a[i + 1] - 1 - sum + a[i] - 1) / a[i];
            
			//更新已经求的的面额范围sum
			sum += k * a[i];
            
            //跟新结果
            ans += k;
        }
        cout<<ans<<endl;
    }
    return 0;
}
0

评论区