首页 > 代码库 > P2376 [USACO09OCT]津贴Allowance
P2376 [USACO09OCT]津贴Allowance
P2376 [USACO09OCT]津贴Allowance
题目背景
作为学习刻苦、成绩优秀的回报，妈妈决定开始每个星期给杀马特一点零花钱。
题目描述
作为创造产奶纪录的回报，Farmer John决定开始每个星期给Bessie一点零花钱。
FJ有一些硬币，一共有N (1 <= N <= 20)种不同的面额。每一个面额都能整除所有比它大的面额。
他想用给定的硬币的集合，每个星期至少给Bessie某个零花钱的数目C (1 <= C <= 100000000)。请帮他计算他最多能支付多少个星期的零花钱。
输入输出格式
输入格式：
第1行: 两个由空格隔开的整数: N 和 C；
第2到第N+1行: 每一行有两个整数表示一个面额的硬币：硬币面额V (1 <= V <= 100,000,000)拥有的该面额的硬币数B (1 <= B <= 1,000,000)。
输出格式：
第1行: 一个单独的整数，表示最多能给支付多少个星期至少为C的零用钱。
输入输出样例
输入样例#1：
3 610 11 1005 120
输出样例#1：
111
说明
【样例说明】
杀马特的妈妈想要每个星期给杀马特六美分。他有100个1美分硬币，120个5美分硬币，和一个10美分硬币。他妈妈可以在一个星期超额付给杀马特一个10美分硬币，然后接下来的10个星期每星期付给杀马特两个5美分硬币。最后100个星期每星期付给杀马特一个1美分硬币跟一个5美分硬币。
分析：贪心。
因为每一个面额都能整除所有比它大的面额。所以小的面额的硬币一定可以凑成大的硬币。
所以我们可以先按照货币面值大小排序，从大到小开始，如果比 c 大，直接加上这个面值的硬币的数量，如果不能达到，拿小的凑。
1 #include<cstdio> 2 #include<algorithm> 3 4 using namespace std; 5 6 struct moy{ 7 int x,y; 8 bool operator < (const moy a) const 9 {10 return x < a.x;11 }12 }t[25];13 int h[25]; //已经使用的硬币数 14 int n,c,p,ans;15 16 int main()17 {18 scanf("%d%d",&n,&c);19 for (int i=1; i<=n; ++i)20 scanf("%d%d",&t[i].x,&t[i].y);21 22 sort(t+1,t+n+1);23 p = n+1;24 while (t[--p].x>=c) ans += t[p].y; 25 while (1)26 {27 int s = c; //s剩余的钱 28 for (int i=p; i>=1; --i)29 {30 int cnt = min(t[i].y, s/t[i].x);31 s -= t[i].x*cnt; //cnt使用硬币的数量 32 h[i] = cnt;33 }34 if (s>0)35 for (int i=1; i<=p && s>0; ++i)36 if (t[i].y>h[i]) s -= t[i].x, h[i]++;37 if (s<=0)38 {39 int cnt = 1e9;40 for (int i=1; i<=p; ++i)41 if (h[i]) cnt = min(cnt,t[i].y/h[i]); //cnt有多少可以这样，搭配的组合 42 ans += cnt;43 for (int i=1; i<=p; ++i)44 if (h[i]) t[i].y -= cnt*h[i];45 }46 else break; 47 }48 printf("%d",ans);49 return 0;50 }
P2376 [USACO09OCT]津贴Allowance
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。