Allowance
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.
Output
* Line 1: A single integer that is the number of weeks Farmer John can pay Bessie at least C allowance
Sample Input
3 6
10 1
1 100
5 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.
Source
题目类型：贪心
算法分析：题目中有一句话说到面值大的钱币的面值是小面值的整数倍，所以贪心策略是优先选择面值大的钱币，因为若选择小面值的钱币，在组成大于等于c的过程中其价钱总会先到达大面值(大面值是小面值的整数倍)，则此时选用大面值替换小面值会更优。然后对于小于c的当前价钱，贪心地选择能使得当前价钱大于c且大于的最小的面值
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 |
/************************************************* Author :supermaker Created Time :2016/4/12 13:28:35 File Location :C:\Users\abcd\Desktop\TheEternalPoet **************************************************/ #pragma comment(linker, "/STACK:102400000,102400000") #include <set> #include <bitset> #include <list> #include <map> #include <stack> #include <queue> #include <deque> #include <string> #include <vector> #include <ios> #include <iostream> #include <fstream> #include <sstream> #include <iomanip> #include <algorithm> #include <utility> #include <complex> #include <numeric> #include <functional> #include <cmath> #include <ctime> #include <climits> #include <cstdarg> #include <cstdio> #include <cstdlib> #include <cstring> #include <cctype> #include <cassert> using namespace std; #define CFF freopen ("aaa.txt", "r", stdin) #define CPPFF ifstream cin ("aaa.txt") #define DB(ccc) cout << #ccc << " = " << ccc << endl #define PB push_back #define MP(A, B) make_pair(A, B) typedef long long LL; typedef unsigned long long ULL; typedef double DB; typedef pair <int, int> PII; typedef pair <int, bool> PIB; const int INF = 0x7F7F7F7F; const int MOD = 1e9 + 7; const double EPS = 1e-10; const double PI = 2 * acos (0.0); const int maxn = 66; struct Node { int c, num; bool operator < (const Node a) const { return c < a.c; } }; Node aa[66]; int used[maxn]; int main() { //CFF; //CPPFF; int n, c; while (scanf ("%d%d", &n, &c) != EOF) { for (int i = 1; i <= n; i++) scanf ("%d%d", &aa[i].c, &aa[i].num); sort (aa + 1, aa + 1 + n); int res = 0; while (1) { int tt = c; memset (used, 0, sizeof (used)); for (int i = n; i >= 1; i--) if (tt > 0) { used[i] = min (aa[i].num, tt / aa[i].c); tt -= used[i] * aa[i].c; } if (tt > 0) for (int i = 1; i <= n; i++) if (aa[i].num > 0 && aa[i].c >= tt) { used[i]++; tt = 0; break; } if (tt > 0) break; int minval = INF; for (int i = 1; i <= n; i++) if (used[i]) minval = min (minval, aa[i].num / used[i]); res += minval; for (int i = 1; i <= n; i++) if (used[i]) aa[i].num -= minval * used[i]; } printf ("%d\n", res); } return 0; } |
- « 上一篇：poj3187
- poj3262：下一篇 »