一、题意:约翰要给他的牛贝西发工资,每天不得低于C元,约翰有n种面值的钱币,第i种的面值为v_i,数量有b_i。问这些钱最多给贝西发多少天的工资。注意,每种面值的金钱都是下一种的面值的倍数。
二、思路:分三步解决:1. 按照面值从大到小取,面值大于等于C的,直接取光。2. 再按面值从大到小取,凑近C,可以小于等于C,但不能大于C.3.最后从小到大取,凑满C,这里的凑满可以等于大于C。然后将上述2,3步取到的面值全部取走,再转入步骤2,这样每次找到的取法就是当前最优取法,直到所剩下的金币总价值不够C结束。
三、代码:
1 #include2 #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 }