题目链接:
http://acm.hdu.edu.cn/showproblem.php?pid=3348
题目大意:
给你一个价格,还有面值分别为1,5,10,50,100(单位:毛)纸币的数量,要你用最少数量的纸币和最多数量的凑出这个价格,输出最少和最多的数量。
思路:
最少的数量要用贪心的思想,优先取面值尽量大 的纸币来凑这个价格。
最多的数量通过对立事件来凑,通过贪心来凑出sum-n(sum为给的纸币的总价格,n为题目要求凑的价格),如果用贪心的方法凑出sum-n的最小纸币数x,那么凑出n的最大纸币数 = 总纸币数 - x
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
const int maxn = 1e4 + ;
const int INF = << ;
int T, n;
int a[];
int c[] = {,,,,};
int sum, tot;
int solve(int x)
{
int cnt = ;
for(int i = ; i >= ; i--)
{
if(x >= c[i])
{
for(int j = ; j <= a[i] && x >= c[i]; j++)
{
cnt++;
x -= c[i];
//cout<<x<<" "<<c[i]<<endl;
}
}
}
return x == ? cnt : -;
}
int main()
{
cin >> T;
while(T--)
{
cin >> n;
sum = ;
tot = ;
for(int i = ; i < ; i++)
{
cin >> a[i];
sum += a[i] * c[i];//总金额
tot += a[i];//总纸币数目
}
int c = solve(n);//求n元的最小纸币数目
if(c == -)
{
printf("-1 -1\n");
}
else
{
int d = tot - solve(sum - n);//求sum-n元的最小纸币数目,就可以求出n元的最大纸币数目
printf("%d %d\n", c, d);
}
}
return ;
}
hdu-3348 coins---贪心的更多相关文章
-
hdu 3348 coins
这道题算是一道很经典的题,很好的诠释了贪心和动态规划的不同功能.求最少钱的数量用贪心就够了,但是求最多钱的数量要用到动态规划的思想,每步都尽量保留最大 数量.具体看程序注解: #include&quo ...
-
HDOJ(HDU).2844 Coins (DP 多重背包+二进制优化)
HDOJ(HDU).2844 Coins (DP 多重背包+二进制优化) 题意分析 先把每种硬币按照二进制拆分好,然后做01背包即可.需要注意的是本题只需要求解可以凑出几种金钱的价格,而不需要输出种数 ...
-
背包系列练习及总结(hud 2602 &;&; hdu 2844 Coins &;&; hdu 2159 &;&; poj 1170 Shopping Offers &;&; hdu 3092 Least common multiple &;&; poj 1015 Jury Compromise)
作为一个oier,以及大学acm党背包是必不可少的一部分.好久没做背包类动规了.久违地练习下-.- dd__engi的背包九讲:http://love-oriented.com/pack/ 鸣谢htt ...
-
Hdu 4864(Task 贪心)(Java实现)
Hdu 4864(Task 贪心) 原题链接 题意:给定n台机器和m个任务,任务和机器都有工作时间值和工作等级值,一个机器只能执行一个任务,且执行任务的条件位机器的两个值都大于等于任务的值,每完成一个 ...
-
D - 淡黄的长裙 HDU - 4221(贪心)
D - 淡黄的长裙 HDU - 4221(贪心) James is almost mad! Currently, he was assigned a lot of works to do, so ma ...
-
hdu 2037简单贪心--活动安排问题
活动安排问题就是要在所给的活动集合中选出最大的相容活动子集合,是可以用贪心算法有效求解的很好例子.该问题要求高效地安排一系列争用某一公共资源的活动.贪心算法提供了一个简单.漂亮的方法使得尽可能多的活动 ...
-
HDU 4864 Task (贪心+STL多集(二分)+邻接表存储)(杭电多校训练赛第一场1004)
题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=4864 解题报告:有n台机器用来完成m个任务,每个任务有一个难度值和一个需要完成的时间,每台机器有一个可 ...
-
HDU 4310 Hero (贪心算法)
A - Hero Time Limit:3000MS Memory Limit:65536KB 64bit IO Format:%I64d & %I64u Submit Sta ...
-
hdu 4268 multiset+贪心
Alice和Bob有n个长方形,有长度和宽度,一个矩形可以覆盖另一个矩形的条件的是,本身长度大于等于另一个矩形,且宽度大于等于另一个矩形,矩形不可旋转,问你Alice最多能覆盖Bob的几个矩形? /* ...
-
hdu 4864 Task (贪心 技巧)
题目链接 一道很有技巧的贪心题目. 题意:有n个机器,m个任务.每个机器至多能完成一个任务.对于每个机器,有一个最大运行时间xi和等级yi, 对于每个任务,也有一个运行时间xj和等级yj.只有当xi& ...
随机推荐
-
在ASP学习当中对双引号,单引号以及&;符号的理解
在我的Web安全学习的开始需要对ASP的代码有一定的熟悉程度但是在查看源码的时候经常性的看到双引号,单引号以及&号.并且对他们的用法经常产生疑惑的地方,这里是我搜集的一些理解和感悟,以期对AS ...
-
js的继承
js要实现继承有很多方法,个人总结大致分为三种: function people(){ this.specials = "人类"; } function p1(name){ thi ...
-
在iOS中怎样创建可展开的Table View?(上)
原文地址 本文作者:gabriel theodoropoulos 原文:How To Create an Expandable Table View in iOS 原文链接 几乎所有的app都有一个共 ...
-
Altium Designer 覆铜时过孔连接形式的设置——只将过孔连接设置为Direct Connect
Altium Designer 在PCB覆铜时,所有的过孔和焊盘都是十字连接即Relief Connect连接的,没有像PROTEL 99SE一样只有接地的焊盘才是十字连接而过孔是直接连接的. 如下图 ...
-
Java、javax、org、sun、Java.util等常用包的区别、详解、实例
Java.javax.org.sun包都是jdk提供的类包,且都是在rt.jar中.rt.jar是JAVA基础类库(java核心框架中很重要的包),包含lang在内的大部分功能,而且rt.jar默认就 ...
-
Kubernetes---存储
pod中定义需要的存储卷,类型为pvc pvc 与 pv 建立绑定关系 kubectl explain pv 定义pv时不要加namspce
-
clean 伪目标
下面的"clean"目标,是一个"伪目标", clean: rm *.o temp 我们生成了许多文件编译文件,我们也应该 ...
-
有关Linux的.a、.so和.o文件(转)【原文章有些错误,自己已更改】
gcc 生成 .a静态库和 .so动态库 我们通常把一些公用函数制作成函数库,供其它程序使用.函数库分为静态库和动态库两种.静态库在程序编译时会被连接到目标代码中,程序运行时将不再需要该静态库.动态库 ...
-
阿里云Maven settings.xml文件
<?xml version="1.0" encoding="UTF-8"?> <!-- Licensed to the Apache Soft ...
-
Linux内核同步机制之(四):spin lock【转】
转自:http://www.wowotech.net/kernel_synchronization/spinlock.html 一.前言 在linux kernel的实现中,经常会遇到这样的场景:共享 ...