贪心-HDU3348 coins(钱币问题)

布满荆棘的人生 2023-03-13 02:48 27阅读 0赞

### 文章目录 ###

*  题目
 *   *  题意
     *  分析
     *  代码

# 题目 #

--------------------

传送门: [HDU-3348][]

> “Yakexi, this is the best age!” Dong MW works hard and get high pay, he has many 1 Jiao and 5 Jiao banknotes(纸币), some day he went to a bank and changes part of his money into 1 Yuan, 5 Yuan, 10 Yuan.(1 Yuan = 10 Jiao)  
> “Thanks to the best age, I can buy many things!” Now Dong MW has a book to buy, it costs P Jiao. He wonders how many banknotes at least,and how many banknotes at most he can use to buy this nice book. Dong MW is a bit strange, he doesn’t like to get the change, that is, he will give the bookseller exactly P Jiao.

**input:**

> T(T<=100) in the first line, indicating the case number.  
> T lines with 6 integers each:  
> P a1 a5 a10 a50 a100  
> ai means number of i-Jiao banknotes.  
> All integers are smaller than 1000000.

**output:**

> Two integers A,B for each case, A is the fewest number of banknotes to buy the book exactly, and B is the largest number to buy exactly.If Dong MW can’t buy the book with no change, output “-1 -1”.

**Sample Input:**

3
    33 6 6 6 6 6
    10 10 10 10 10 10
    11 0 1 20 20 20

**Sample Output:**

6 9
    1 10
    -1 -1

## 题意 ##

分别给出1，5，10，50，100角面值的纸币张数，求凑出p角的最小张数和最大张数。

## 分析 ##

*  最小：每次贪心选择面值最大的纸币来凑成p角，凑不成则输出-1。
 *  最大：用对立反面来求，用最小张数凑成它的反面，那么剩余张数就是凑成p的最大张数。设所有纸币组成总价值sum和纸币总数cnt，用上一点求凑成(sum-p)最小张数x，cnt-x即可。

## 代码 ##

#include<cstdio>
    #include<algorithm>
    using namespace std;
    const int maxn = 1000006;
    int t, p, a[5], b[5] = {  1,5,10,50,100 };
    int mi, ma, sum, cnt, fp, ti;
    int main() { 
    	scanf("%d", &t);
    	while (t--) { 
    		scanf("%d%d%d%d%d%d", &p, &a[0], &a[1], &a[2], &a[3], &a[4]);
    		mi = ma = sum = cnt = 0;
    		for (int i = 0; i <= 4; i++) { 
    			sum += b[i] * a[i];//纸币总价值
    			cnt += a[i];//纸币总数
    		}
    		fp = sum - p;
    		for (int i = 4; i >= 0; i--) { 
    			ti = p / b[i];//最多换b[i]面值几张
    			if (ti > a[i])ti = a[i];//超过题目输入张数
    			mi += ti;
    			p -= ti * b[i];
    		}
    		if (p) { 
    			printf("-1 -1\n");
    			continue;
    		}
    		for (int i = 4; i >= 0; i--) { 
    			ti = fp / b[i];
    			if (ti > a[i])ti = a[i];
    			ma += ti;
    			fp -= ti * b[i];
    		}
    		printf("%d %d\n", mi, cnt - ma);
    	}
    	return 0;
    }

> **原创不易，请勿转载**（本不富裕的访问量雪上加霜 ）  
> 博主首页：[https://blog.csdn.net/qq\_45034708][https_blog.csdn.net_qq_45034708]  
> *如果文章对你有帮助，记得关注点赞收藏❤*

[HDU-3348]: http://acm.hdu.edu.cn/showproblem.php?pid=3348
[https_blog.csdn.net_qq_45034708]: https://blog.csdn.net/qq_45034708