11选五5爱彩乐
首頁 > 其他 > 詳細

洛谷 1658 購物

時間:2018-05-28 20:55:58      閱讀:394      評論:0      收藏:0      [點我收藏+]

標簽:org   需要   購物   display   con   價值   滿足   In   100%   

              洛谷 1658 購物

題目描述

你就要去購物了,現在你手上有N種不同面值的硬幣,每種硬幣有無限多個。為了方便購物,你希望帶盡量少的硬幣,但要能組合出1到X之間的任意值。

輸入輸出格式

輸入格式:

第一行兩個數X、N,以下N個數,表示每種硬幣的面值。

【數據規模】

對于30%的數據,滿足N≤3,X≤20;

對于100%的數據,滿足N≤10,X≤1000.

輸出格式:

最少需要攜帶的硬幣個數,如果無解輸出-1.

輸入輸出樣例

輸入樣例#1: 
20 4
1 2 5 10
輸出樣例#1: 
5
題解:
這道題我記得我們之前考過,當時傻,所以并不會。就騙了三十分,hhh。
當時是我們區學長出的題,其實我們區除了hmq之外的學長都是挺有人性的。
這道題主要是用到了貪心的思想,

每一次都要在找到比當前該湊數錢小的最大面值數,這樣就可以在錢幣數量相同的情況下可拼湊價值最大。
代碼:
技術分享圖片
 1 #include<iostream>
 2 #include<cstdio>
 3 #include<algorithm>
 4 const int maxn=1005;
 5 int i,j,n,x,s[maxn],ans,sum;
 6 int main() {
 7     std::cin>>x>>n;
 8     for(i=0; i<n; i++) std::cin>>s[i];
 9     std::sort(s,s+n);
10     if(s[0]!=1) {
11         puts("-1");return 0;
12     }
13     while(sum<x) {
14         for(i=n-1; i>=0; i--)
15             if(s[i]<=sum+1) break;
16         ans++;sum+=s[i];
17     }
18     printf("%d\n",ans);
19     return 0;
20 }
View Code

 

 

洛谷 1658 購物

標簽:org   需要   購物   display   con   價值   滿足   In   100%   

原文:https://www.cnblogs.com/GTBA/p/9102077.html

(0)
(0)
   
舉報
評論 一句話評論(0
0條  
登錄后才能評論!
? 2014 bubuko.com 版權所有 魯ICP備09046678號-4
打開技術之扣,分享程序人生!
             

魯公網安備 37021202000002號

11选五5爱彩乐