洛谷(P1658购物C++)-创新互联
题目描述:
为饶平等地区用户提供了全套网页设计制作服务,及饶平网站建设行业解决方案。主营业务为成都网站制作、成都网站设计、饶平网站设计,以传统方式定制建设网站,并提供域名空间备案等一条龙服务,秉承以专业、用心的态度为用户提供真诚的服务。我们深信只要达到每一位用户的要求,就会得到认可,从而选择与我们长期合作。这样,我们也可以走得更远!你就要去购物了,现在你手上有 N种不同面值的硬币,每种硬币有无限多个。为了方便购物,你希望带尽量少的硬币,但要能组合出 1到 X 之间的任意值。
输入格式:
第一行两个数 X, N,以下 N 个数,表示每种硬币的面值。
输出格式:
最少需要携带的硬币个数,如果无解输出 -1
。
输入输出样例:
输入:20 4 输出:5
1 2 5 10
解题思路:
这道题是一道经典的贪心问题,你得先弄清楚贪心策略
首先,我们必须得有一枚1元面值的硬币,如果没有的话,就是无解,因为你凑不出1元。
下面我们就得列举找规律了(先不按每种面值无限张算,就按每种只有一张算):
有了面值1元,就一定要有面值2元的,不然你凑不出2元:
目前面值:1元、2元
接着想,需不需要3元呢?其实是不需要的,因为1元和2元可以凑出3元;
目前面值:1元、2元
那四元呢?那就必须要了,无论用前面所有的面值也凑不到4元。
目前面值:1元、2元、4元
五元?可以用1元和4元凑成,不用! 目前面值:1元、2元、4元
六元?可以用2元和4元凑成,不用! 目前面值:1元、2元、4元
七元?可以用1元、2元和4元凑成,不用! 目前面值:1元、2元、4元
八元?前面三个面值怎么也凑不成,必须要用! 目前面值:1元、2元、4元、8元
以此类推会得到这样的数列:1元、2元、4元、8元、16元、32元、64元……
由次我们发现了一个规律:每新来一枚硬币,它的值只可能小于等于前面所有面值和+1
知道了贪心策略,代码就迎刃而解了!
参考代码:
#includeusing namespace std;
int main()
{
int sum,cnt,n,x,a[1005];//sum表示目前硬币面值总和,cnt表示硬币数
cin>>x>>n;
for(int i=1;i<=n;i++) cin>>a[i];
sort(a+1,a+n+1);//从小到大排序,保证小的在前
//如果没有一元的硬币,就凑不出1元,所以无解
if(a[1]!=1)
{
cout<<"-1"<
我还是一名小学生,程序有点繁琐,希望大家能支持一下!
你是否还在寻找稳定的海外服务器提供商?创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源,准确流量调度确保服务器高可用性,企业级服务器适合批量采购,新人活动首月15元起,快前往官网查看详情吧
本文题目:洛谷(P1658购物C++)-创新互联
文章源于:http://scyanting.com/article/cogsoj.html