题意:

给定6个硬币的币值, 问组成1~100这些数最少要几个硬币, 比如给定1 2 5 10 20 50, 组成40 可以是 20 + 20, 也可以是 50 -10, 最少硬币是2个。

分析:

这道题可以转化成是一道最短路的方法去做, 设一开始的起点为0(什么硬币都不取), 然后每个点都有12条路(对应正负6种币值), 每条路的权值为1,

令dis[maxn]初始化为inf, 求出dis[1]~dis[100]即可。

但是最大值maxn要取比100更大, 比如 构造100的最优方法为51+51-1-1. 那么我们就需要102面值金钱的构造dist[102] 才能正确的推出dist[100], 虽然不知道这个最大值多少,但这个最大值取200可以过这题。

 #include <cstdio>
#include <iostream>
#include <queue>
#include <cstring>
#define mem(a) memset(a, 0, sizeof(a))
using namespace std;
const int maxn = ;
const int inf = 1e9;
int coin[];
int dis[maxn];
int vis[maxn];
void spfa(){
mem(vis);
queue<int> q;
fill(dis,dis+maxn, inf);
dis[] = ;
vis[] = ;
q.push();
while(!q.empty()){
int u = q.front();
for(int i = ; i < ; i++){
int v = u + coin[i];
if(v < || v > ) continue;//如果点v是负数, 那么不需要入队。
if(dis[v] > dis[u] + ){
dis[v] = dis[u] + ;
if(!vis[v]){
vis[v] = ;
q.push(v);
}
}
}
// vis[u] = 0; 这里其实不用标记, 因为每个点只会入队一次,边的权值都是1, 怎么扩展都是最短路
q.pop();
}
}
int main()
{
int t;
cin >> t;
while ( t -- ) {
for ( int i = ; i < ; ++ i ){
cin >> coin[ *i ];
coin[ * i + ] = -coin[ * i];//构造币值为负数的硬币
}
spfa();
double sum = 0.0;
int maxdis = ;
for ( int i = ; i <= ; ++ i ) {
sum += dis [i];
if ( dis[i] > maxdis )
maxdis = dis[i];
}
printf("%.2f %d\n",sum/100.0, maxdis);
}
return ;
}

最新文章

  1. Webstorm编译TypeScript
  2. 登录FTP,下载并读取文件内容
  3. 用花生壳实现内网映射,决解无域名、无公网IP、无服务器空间问题
  4. (转载)IO-同步、异步、阻塞、非阻塞
  5. IIS错误500.21
  6. Eclipse中出现Select at least one project解决办法
  7. JAVA的instanceOf什么时候用啊
  8. Chapter 15_2 编写模块的基本方法
  9. 聊一聊JQ中delegate事件委托的好处
  10. ajax请求获取实时数据
  11. freemind中内容变成html转义字符解决方法
  12. jQuery基础操作
  13. 炫龙炎魔T1笔记本 Win7 系统安装
  14. 百战程序员——JSP
  15. Python基础之条件语句和循环
  16. Vue插件plugins的基本操作
  17. IO流_文件切割与合并
  18. ASP.NET Core入门系列教程
  19. 20180925 SQL Server游标使用
  20. 05 面向对象:构造方法&amp;static&amp;继承&amp;方法 &amp;final

热门文章

  1. [WOJ2549]逻辑的连通性
  2. 题解报告:hdu 4135 Co-prime(容斥定理入门)
  3. Suricata的配置
  4. android开发学习 ------- Error:Failed to open zip file.
  5. Java程序操作数据库SQLserver详解
  6. JSP报错The value for the useBean class attribute *** is invalid.
  7. java实现汉诺塔算法
  8. SQLite -分离数据库
  9. day24-2 单例模式
  10. QT+模态对话框与非模态对话框