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.
思路：这道题只需要知道付工资的时候如果组合不出来适合的面值的工资，就要从小到大来选择面额来使超出的金钱最少。
然后在每次的找到适合面值组合中，减去他们最少的面值数量。这道题大概就可以按照这样的思路直白的写出来了。
C++版本一
#include<stdio.h>
#include<string.h>
#include<iostream>
#include<algorithm>
using namespace std;
const int maxn=30;
struct node
{
int x,y;//存储钱的大小和数量
bool operator<(const node c)const
{
return x>c.x;
}
}num[maxn];
int need[maxn],n,c,kj;
//need[]函数是是存储需要哪些钱币的组合
int main()
{
while(scanf("%d%d",&n,&c)!=EOF)
{
for(int i=0;i<n;i++)
scanf("%d%d",&num[i].x,&num[i].y);
sort(num,num+n);//排序是第一步
kj=0;
while(1)
{
int sum=c;
memset(need,0,sizeof(need));
for(int i=0;i<n;i++)//这个for循环是用于找出钱币的组合方法
{
if(sum>0)
{
int t=sum/num[i].x;
if(t==0)
continue;
t=min(t,num[i].y);
need[i]=t;
sum-=t*num[i].x;
}
}
if(sum>0)//如果在上面的组合中没有使sum变为0,则从小到大选择最小的面值组合，这样使面值超过的最小化
{
for(int i=n-1;i>=0;i--)
if(num[i].y&&num[i].x>=sum)
{
sum=0;
need[i]++;
break;
}
}
if(sum>0)//如果组合不能达到c，怎么说明搜索结束
break;
int cc=2e9;
for(int i=n-1;i>=0;i--)//找出这个组合成的面值中最小的数量，同时减去它们。
{
if(need[i])
{
cc=min(cc,num[i].y/need[i]);
}
}
kj+=cc;
for(int i=0;i<n;i++)
if(need[i])
{
num[i].y-=cc*need[i];
}
}
printf("%d\n",kj);
}
return 0;
}
C++版本二
/*大于C的coin每周一个发给Bessie就好了
小于C的：
从cent最大的开始取，凑近C但不能等于C
从cent最小的开始取，等于或大于C
*/
#include<cstdio>
#include<algorithm>
using namespace std;
const int MAX_N = 25;
int N, C, ans;
struct coin {
int cent;
int num;
} a[MAX_N];
bool cmp(coin b, coin c)
{
return b.cent > c.cent;
}
void init()
{
ans = 0;//需要吗？
for(int i=0; i<N; i++){
scanf("%d%d", &a[i].cent, &a[i].num);
}
}
void f()
{
int i, j = N-1, sum = 0;
for(i=0; i<N && a[i].cent>=C; i++){
ans += a[i].num;
a[i].num = 0;
}
out:
for(i=0; i<N; i++){
while(a[i].num>0){
//从cent最大的开始取凑近或等于C但不大于C
sum += a[i].cent;
a[i].num--;
if(sum == C){
ans++; sum = 0;
goto out;
}
else if(sum > C){
sum -= a[i].cent;
a[i].num++;
break;
}
}
}
//从cent最小的开始取直到凑够C
for(; j>=0; j--){
while(a[j].num > 0){
sum += a[j].cent;
a[j].num--;
if(sum >= C){
ans++; sum = 0;
goto out;
}
}
}
}
int main()
{
while(~scanf("%d%d", &N, &C)){
init();
sort(a, a+N, cmp);
f();
printf("%d\n", ans);//记得删\n!!!
}
return 0;
}
C++版本三
思路：第一时间肯定是想到浪费的越少越好。
1. 当币值大于C的时候，就直接用这个硬币付工资。
2. 当币值小于C的时候，就要想一种搭配方案，使得总的价值等于或者多于C但多余的钱要尽可能少，这个就比较难想到了。
而题目中有一个条件是，大的币值能被小的整除，所以若干个小的一定能凑出大的，那么可以用一个大的或若干个小的的情况下，肯定是要选用一个大的，这样之后的搭配方案才能更好的符合”超出C的钱尽可能少“这个条件。
所以， 当当币值小于C的时候，从币值最大的开始遍历，一个小于C，那两个、三个一直到n个，直到刚好等于C或者n+1个硬币大于C，如果是后者，那就选n个，在从币值更小的硬币重复上面的过程，直到刚好等于C或者全部硬币遍历完
如果最后的全部遍历完还是不能凑到刚好等于C，那么从小到大，直到找到一个加上这个硬币刚好大于C的。如果找不到，就说明剩下的全部加起来已经没有C了，结束了
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
using namespace std;
const int MAXN = 25;
pair<int,int> p[MAXN];//存储硬币币值和数量
int n, c;
int main()
{
while(scanf("%d%d", &n, &c) == 2)
{
for(int i=0; i<n; i++)
scanf("%d%d", &p[i].first, &p[i].second);
sort(p, p+n);//按币值从小到大排序
int ans = 0, require, need[MAXN], rest;
while(true)
{
rest = c;
memset(need, 0, sizeof(need));
for(int i=n-1; i>=0; --i)//从大到小选择
{
if(p[i].second>0)
{
require = min(p[i].second, rest/p[i].first);//需要这个币值的硬币的数量
rest -= require*p[i].first;
need[i] = require;
}
if(rest == 0) break;//刚好凑出C
}
if(rest)
{
for(int i=0; i<n; i++)//从小到大选择
{
if(p[i].second && p[i].first>=rest)//加上这个硬币（最小）就刚好大于C
{
rest = 0;
need[i]++;
break;
}
}
}
if(rest) break;//两轮选择后仍然凑不齐C，结束
int week = 1e8;//用这个方案能发多少个星期的工资
for(int i=0; i<n; i++)
{
if(need[i]) week = min(week, p[i].second/need[i]);
}
ans+=week;
for(int i=0; i<n; i++)//把用掉的硬币减去
{
if(need[i]) p[i].second -= week*need[i];
}
}
cout << ans << endl;
}
return 0;
}
京公网安备 11010502036488号