Problem Description
"Yakexi, this
is the best age!" Dong MW works hard and get high pay, he has many
1 Jiao and 5 Jiao banknotes(纸币), some day he went to a bank and
changes part of his money into 1 Yuan, 5 Yuan, 10 Yuan.(1 Yuan = 10
Jiao)
"Thanks to the best age, I can buy many things!" Now Dong MW has a
book to buy, it costs P Jiao. He wonders how many banknotes at
least,and how many banknotes at most he can use to buy this nice
book. Dong MW is a bit strange, he doesn't like to get the change,
that is, he will give the bookseller exactly P Jiao.
is the best age!" Dong MW works hard and get high pay, he has many
1 Jiao and 5 Jiao banknotes(纸币), some day he went to a bank and
changes part of his money into 1 Yuan, 5 Yuan, 10 Yuan.(1 Yuan = 10
Jiao)
"Thanks to the best age, I can buy many things!" Now Dong MW has a
book to buy, it costs P Jiao. He wonders how many banknotes at
least,and how many banknotes at most he can use to buy this nice
book. Dong MW is a bit strange, he doesn't like to get the change,
that is, he will give the bookseller exactly P Jiao.
Input
T(T<=100)
in the first line, indicating the case number. T lines with 6
integers each: P a1 a5 a10 a50 a100 ai means number of i-Jiao
banknotes. All integers are smaller than 1000000.
in the first line, indicating the case number. T lines with 6
integers each: P a1 a5 a10 a50 a100 ai means number of i-Jiao
banknotes. All integers are smaller than 1000000.
Output
Two integers
A,B for each case, A is the fewest number of banknotes to buy the
book exactly, and B is the largest number to buy exactly.If Dong MW
can't buy the book with no change, output "-1 -1".
A,B for each case, A is the fewest number of banknotes to buy the
book exactly, and B is the largest number to buy exactly.If Dong MW
can't buy the book with no change, output "-1 -1".
Sample Input
3
33 6 6 6 6
6
6
10 10 10 10
10 10
10 10
11 0 1 20
20 20
20 20
Sample Output
6 9
1 10
-1 -1
题意：有1 5 10
50 100这几种面值的钱，且个数是给定的，给你一个钱数，让你求最多硬币树，和最少硬币数；
50 100这几种面值的钱，且个数是给定的，给你一个钱数，让你求最多硬币树，和最少硬币数；
解题思路：求最小钱数当然好求，从大到小开始贪心，但是求最多硬币数的时候就有点问题了，试了很多种方法，可以用小硬币来去换已经球出来的最小硬币的个数，还完了可能就是最大的了；
感悟：这两天做题有点慢，每个题都得先先想，而且还有很多没见过的东西，还得先查资料，得加快进度了。
代码：
#include
#include
#include
using namespace std;
int mina(int a[],int p,int a_m[])
{
int
ans=0;
for(int
i=5;i>1;i--)
{
if(p>=a[i]*a_m[i])//看看当前剩下的钱是不是比枚举到的钱数大
{
ans+=a[i];
p-=a[i]*a_m[i];
}
else//小
{
ans+=p/a_m[i];
p%=a_m[i];
}
}
if(p>a[1]) return -1;
else return
ans+p;
}
int maxa(int a[],int p,int a_m[],int sum[])
{
int
ans=0;
for(int
i=5;i>1;i--)
{
if(p<=sum[i-1])//p比当前金币的总价值小
continue;
else//大
{
int t;
t=((p-sum[i-1])/a_m[i])+(((p-sum[i-1])%a_m[i])?1:0);
//(p-sum[i-1])是除去当前钱数之前的钱数之和
ans+=t;
p-=t*a_m[i];
//printf("t=%d a[i]_m=%d p=%d\n",t,a_m[i],p);
}
}
//printf("P=%d a[1]=%d\n",p,a[1]);
if(p>a[1]) return -1;
else return
ans+p;
if(p>a[1]) return -1;
else return
ans+p;
}
int maxa(int a[],int p,int a_m[],int sum[])
{
int
ans=0;
for(int
i=5;i>1;i--)
{
if(p<=sum[i-1])//p比当前金币的总价值小
continue;
else//大
{
int t;
t=((p-sum[i-1])/a_m[i])+(((p-sum[i-1])%a_m[i])?1:0);
//(p-sum[i-1])是除去当前钱数之前的钱数之和
ans+=t;
p-=t*a_m[i];
//printf("t=%d a[i]_m=%d p=%d\n",t,a_m[i],p);
}
}
//printf("P=%d a[1]=%d\n",p,a[1]);
if(p>a[1]) return -1;
else return
ans+p;
}
int solve(int a[],int p,int a_m[])
{
int
minn=0,maxn=0;
int
sum[6]={0};
for(int
i=1;i<6;i++)
sum[i]=sum[i-1]+a[i]*a_m[i];
minn=mina(a,p,a_m);
maxn=maxa(a,p,a_m,sum);
//printf("minn=%d maxn=%d\n",minn,maxn);
if(minn==-1)printf("-1 -1\n");
else
{
if(maxn==-1)printf("-1 -1\n");
else
printf("%d %d\n",minn,maxn);
}
}
int main()
{
//freopen("in.txt", "r", stdin);
int
a[6],a_m[6]={0,1,5,10,50,100},sum=0,n,p;
scanf("%d",&n);
for(int
i=0;i
{
memset(a,0,sizeof(a));
scanf("%ld%ld%ld%ld%ld%ld",&p,&a[1],&a[2],&a[3],&a[4],&a[5]);
int solve(int a[],int p,int a_m[])
{
int
minn=0,maxn=0;
int
sum[6]={0};
for(int
i=1;i<6;i++)
sum[i]=sum[i-1]+a[i]*a_m[i];
minn=mina(a,p,a_m);
maxn=maxa(a,p,a_m,sum);
//printf("minn=%d maxn=%d\n",minn,maxn);
if(minn==-1)printf("-1 -1\n");
else
{
if(maxn==-1)printf("-1 -1\n");
else
printf("%d %d\n",minn,maxn);
}
}
int main()
{
//freopen("in.txt", "r", stdin);
int
a[6],a_m[6]={0,1,5,10,50,100},sum=0,n,p;
scanf("%d",&n);
for(int
i=0;i
{
memset(a,0,sizeof(a));
scanf("%ld%ld%ld%ld%ld%ld",&p,&a[1],&a[2],&a[3],&a[4],&a[5]);
for(int j=1;j<6;j++)
{
sum+=a_m[j]*a[j];
}
if(sum
else solve(a,p,a_m);
}
return
0;
}