hdu-3348 coins---贪心

题目链接:

http://acm.hdu.edu.cn/showproblem.php?pid=3348

题目大意:

给你一个价格,还有面值分别为1,5,10,50,100(单位:毛)纸币的数量,要你用最少数量的纸币和最多数量的凑出这个价格,输出最少和最多的数量。

思路:

最少的数量要用贪心的思想,优先取面值尽量大 的纸币来凑这个价格。

最多的数量通过对立事件来凑,通过贪心来凑出sum-n(sum为给的纸币的总价格,n为题目要求凑的价格),如果用贪心的方法凑出sum-n的最小纸币数x,那么凑出n的最大纸币数 = 总纸币数 - x

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<algorithm>
 5 #include<cmath>
 6 using namespace std;
 7 const int maxn = 1e4 + 10;
 8 const int INF = 1 << 30;
 9 int T, n;
10 int a[10];
11 int c[5] = {1,5,10,50,100};
12 int sum, tot;
13 int solve(int x)
14 {
15     int cnt = 0;
16     for(int i = 4; i >= 0; i--)
17     {
18         if(x >= c[i])
19         {
20             for(int j = 1; j <= a[i] && x >= c[i]; j++)
21             {
22                 cnt++;
23                 x -= c[i];
24                 //cout<<x<<" "<<c[i]<<endl;
25             }
26         }
27     }
28     return x == 0 ? cnt : -1;
29 }
30 int main()
31 {
32     cin >> T;
33     while(T--)
34     {
35         cin >> n;
36         sum = 0;
37         tot = 0;
38         for(int i = 0; i < 5; i++)
39         {
40             cin >> a[i];
41             sum += a[i] * c[i];//总金额
42             tot += a[i];//总纸币数目
43         }
44         int c = solve(n);//求n元的最小纸币数目
45         if(c == -1)
46         {
47             printf("-1 -1
");
48         }
49         else
50         {
51             int d = tot - solve(sum - n);//求sum-n元的最小纸币数目,就可以求出n元的最大纸币数目
52             printf("%d %d
", c, d);
53         }
54     }
55     return 0;
56 }
原文地址:https://www.cnblogs.com/fzl194/p/8697068.html