博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
poj3040
阅读量:6140 次
发布时间:2019-06-21

本文共 1702 字,大约阅读时间需要 5 分钟。

一、题意:约翰要给他的牛贝西发工资,每天不得低于C元,约翰有n种面值的钱币,第i种的面值为v_i,数量有b_i。问这些钱最多给贝西发多少天的工资。注意,每种面值的金钱都是下一种的面值的倍数。

二、思路:分三步解决:1. 按照面值从大到小取,面值大于等于C的,直接取光。2. 再按面值从大到小取,凑近C,可以小于等于C,但不能大于C.3.最后从小到大取,凑满C,这里的凑满可以等于大于C。然后将上述2,3步取到的面值全部取走,再转入步骤2,这样每次找到的取法就是当前最优取法,直到所剩下的金币总价值不够C结束。

三、代码:

1 #include 
2 #include
3 #include
4 #include
5 #include
6 #include
7 #define MAXN 11111 8 #define MAXM 222222 9 #define INF 100000000010 using namespace std;11 int n, c;12 typedef pair
P;13 P a[22];14 int use[22], sum[22];15 int main()16 {17 scanf("%d%d", &n, &c);18 for(int i = 0; i < n; i++) scanf("%d%d", &a[i].first, &a[i].second);19 sort(a, a + n);20 int ans = 0;21 for(int i = n - 1; i >= 0; i--)22 if(a[i].first >= c)23 {24 ans += a[i].second;25 a[i].second = 0;26 }27 while(true)28 {29 int flag = 0;30 int tmp = c;31 32 memset(use, 0, sizeof(use));33 for(int i = n - 1; i >= 0; i--)34 if(a[i].second)35 {36 int k = tmp / a[i].first;37 int mi = min(a[i].second, k);38 tmp -= mi * a[i].first;39 use[i] = mi;40 if(tmp <= 0)41 {42 flag = 1;43 break;44 }45 }46 if(tmp > 0)47 {48 for(int i = 0; i < n; i++)49 if(a[i].second > use[i])50 {51 while(use[i] < a[i].second)52 {53 tmp -= a[i].first;54 use[i]++;55 if(tmp <= 0)56 {57 flag = 1;58 break;59 }60 }61 if(tmp <= 0) break;62 }63 }64 if(!flag) break;65 int mx = INF;66 for(int i = n - 1; i >= 0; i--)67 if(use[i]) mx = min(mx, a[i].second / use[i]);68 ans += mx;69 for(int i = n - 1; i >= 0; i--)70 if(use[i]) a[i].second -= mx * use[i];71 72 }73 printf("%d\n", ans);74 return 0;75 }
View Code

 

  

 

转载于:https://www.cnblogs.com/acm-jing/p/9833190.html

你可能感兴趣的文章
JS日期的方法
查看>>
git 常用操作命令(转)
查看>>
flex上中下布局,header,footer固定
查看>>
此坑待填 离散化思想和凸包 UVA - 10173 Smallest Bounding Rectangle
查看>>
TOJ5272: 逆矩阵
查看>>
程序员何苦为难程序员?
查看>>
MJPhotoBrowser 图片放大时,图片太靠下修改
查看>>
技术沟通者的自我修养
查看>>
【翻译】Sencha Cmd中脚本压缩方法之比较
查看>>
某公司数据恢复报告书
查看>>
某医药公司HP-EVA4400数据恢复报告
查看>>
shell高级视频答学生while循环问题
查看>>
分享Silverlight/Windows8/WPF/WP7/HTML5一周学习导读(5月14日-5月20日)
查看>>
BYOD那些事
查看>>
知识管理与知识工程的区别和联系:管理概念与技术手段
查看>>
Bitlocker企业安全加密管理系列-1
查看>>
SQL Server 高可用性(四)故障转移
查看>>
疯狂ios讲义疯狂连载之图像控件(UIImageView)
查看>>
我的友情链接
查看>>
认识R素材
查看>>