首页 > 代码库 > poj 3040 Allowance
poj 3040 Allowance
Allowance
| Time Limit: 1000MS | Memory Limit: 65536K | |
| Total Submissions: 3008 | Accepted: 1218 |
Description
As a reward for record milk production, Farmer John has decided to start paying Bessie the cow a small weekly allowance. FJ has a set of coins in N (1 <= N <= 20) different denominations, where each denomination of coin evenly divides the next-larger denomination (e.g., 1 cent coins, 5 cent coins, 10 cent coins, and 50 cent coins).Using the given set of coins, he would like to pay Bessie at least some given amount of money C (1 <= C <= 100,000,000) every week.Please help him ompute the maximum number of weeks he can pay Bessie.
Input
* Line 1: Two space-separated integers: N and C
* Lines 2..N+1: Each line corresponds to a denomination of coin and contains two integers: the value V (1 <= V <= 100,000,000) of the denomination, and the number of coins B (1 <= B <= 1,000,000) of this denomation in Farmer John‘s possession.
* Lines 2..N+1: Each line corresponds to a denomination of coin and contains two integers: the value V (1 <= V <= 100,000,000) of the denomination, and the number of coins B (1 <= B <= 1,000,000) of this denomation in Farmer John‘s possession.
Output
* Line 1: A single integer that is the number of weeks Farmer John can pay Bessie at least C allowance
Sample Input
3 610 11 1005 120
Sample Output
111
Hint
INPUT DETAILS:
FJ would like to pay Bessie 6 cents per week. He has 100 1-cent coins,120 5-cent coins, and 1 10-cent coin.
OUTPUT DETAILS:
FJ can overpay Bessie with the one 10-cent coin for 1 week, then pay Bessie two 5-cent coins for 10 weeks and then pay Bessie one 1-cent coin and one 5-cent coin for 100 weeks.
FJ would like to pay Bessie 6 cents per week. He has 100 1-cent coins,120 5-cent coins, and 1 10-cent coin.
OUTPUT DETAILS:
FJ can overpay Bessie with the one 10-cent coin for 1 week, then pay Bessie two 5-cent coins for 10 weeks and then pay Bessie one 1-cent coin and one 5-cent coin for 100 weeks.
题意：有各种面值的钞票，每种都有若干张，每个星期都要用这些钞票的一部分去支付C元及以上的费用，最终要使得支付的星期尽可能的多，那么最多可以支付多少星期
思路：首先按面值从大到小来排序，若钞票的面值大于等于C，只能一张一张先付掉，之后只剩下比C小的钞票，这些钞票进行各种组合使得sum大于C，具体组合方法：
先按面值从大到小循环，用一个数组来记录各种各种面值的钞票各用了多少张，使得总和sum尽可能接近C且比C小一点；第二步：按面值从小到大循环，继续用上面所述数组来记录各种面值的钞票还需要用多少张，最终使得总和sum超过C，但最多只能超过一点点。
组合出sum之后，看看这种组合最多能有几组。之后再进行下一次新的组合……直到所有的组合都用完了，结束。
AC代码：
#define _CRT_SECURE_NO_DEPRECATE#include<iostream>#include<algorithm>using namespace std;const int V_MAX = 20;struct money { int V; int num; bool operator <(const money&b) { return V > b.V; }};money mon[V_MAX];int need[V_MAX];int main() { int N, C; while (cin >> N >> C) { int week = 0; for (int i = 0;i < N;i++) { scanf("%d%d", &mon[i].V, &mon[i].num); if (mon[i].V >= C) { week += mon[i].num;//面值大于C的钱只能一张一星期的给 mon[i].num = 0; } } sort(mon,mon+N);//按面值从大到小排 while (1) {//每一次循环将产生一种能超过sum的钞票组合 int sum = C;//每一种组合要凑足sum memset(need, 0, sizeof(need)); for (int i = 0;i < N;i++) {//面值从大到小 if(sum > 0&&mon[i].num) { int can_use = min(mon[i].num,sum/mon[i].V);//当前面值的钞票的最多能拿几张，尽量多，但不能超过sum if (can_use>0) { sum -= can_use*mon[i].V; need[i] = can_use; } } } for (int i = N - 1;i >= 0;i--) {//面值从小到大 if (sum > 0 && mon[i].num) { int can_use = min(mon[i].num-need[i],(sum+mon[i].V-1)/mon[i].V);//当前面值的钞票尽量多拿，但超过sum一点点就可以了，不要浪费 if (can_use>0) { sum -= can_use*mon[i].V; need[i] += can_use; } } } if (sum > 0) { break; } //至此拼凑出sum需要各种面值的钞票的数量已经都存放在need[]数组中了 int add = INT_MAX; for (int i = 0;i < N;i++) { if (need[i] == 0)continue; add= min(add, mon[i].num / need[i]);//当前的拼凑出sum的组合最多能有几组 } week += add; for (int i = 0;i < N;i++) {//将该组合所使用掉的钞票去除 if (need[i] == 0)continue; mon[i].num -= need[i] * add; } } cout << week << endl; } return 0;}
poj 3040 Allowance
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。