题目描述:
有1,5,10,50,100,500的硬币各C1,C5,C10,C50,C100,C500枚,现在要用这些硬币来支付A元,最少需要多少枚硬币。
解题思路:
贪心算法,竟可能多的使用面值最大的硬币的这一贪心的策略来切了。
# include<cstdio> # include<iostream> using namespace std; const int V[6] = {1,5,10,50,100,500}; int C[6]; int main(void) { int A; while ( cin >> A ) { int ans = 0; for (int i = 0;i < 6;i++ ) { cin>>C[i]; } for ( int i = 5;i >= 0;i-- ) { int t = min(A/V[i],C[i]); A -= t*V[i]; ans+=t; } cout<<ans<<endl; } return 0; }