ICPC 2015 Changchun A Too Rich（贪心）

贪心）"/>

ICPC 2015 Changchun A Too Rich（贪心）

问题 A: Too Rich

时间限制: 1 Sec  内存限制: 128 MB

题目描述

You are a rich person, and you think your wallet is too heavy and full now. So you want to give me some money by buying a lovely pusheen sticker which costs p dollars from me. To make your wallet lighter, you decide to pay exactly p dollars by as many coins and/or banknotes as possible.
For example, if p = 17 and you have two $10 coins, four $5 coins, and eight $1 coins, you will pay it by two $5 coins and seven $1 coins. But this task is incredibly hard since you are too rich and the sticker is too expensive and pusheen is too lovely, please write a program to calculate the best solution.

 

输入

The first line contains an integer T indicating the total number of test cases. Each test case is a line with 11 integers p, c1 , c5 , c10 , c20 , c50 , c100 , c200 , c500 , c1000 , c2000 , specifying the price of the pusheen sticker, and the number of coins and banknotes in each denomination. The number c i means how many coins/banknotes in denominations of i dollars in your wallet.
1≤T≤20000
0≤p≤109
0≤c i≤100000

 

输出

For each test case, please output the maximum number of coins and/or banknotes he can pay for exactly p dollars in a line. If you cannot pay for exactly p dollars, please simply output ‘-1‘.

 

样例输入

3
17 8 4 2 0 0 0 0 0 0 0
100 99 0 0 0 0 0 0 0 0 0
2015 9 8 7 6 5 4 3 2 1 0

 

样例输出

9
-1
36

题意：现在有 1，5,10,20,50,100,200,500,1000,2000面值的钱币，问你要凑够p元钱最多需要多少张纸币，给你p和每个面值纸币的数量
我的想法：但是WA了，首先，我会预处理出来到这个纸币最多能够构成的钱数，面值一共十种，那么我就二进制枚举这一种选还是不选，对于选的，我从后向前跑，对于这一种面值，我尽量少选，一保证前面可以
尽量多选，尽量少选就是最少选一张，最多选给定的数量张，在前面足够构成的情况下选。最后判断是否可以，但是WA了，我想应该是20,50,500，那里的问题，但是还没有找到反例。
找反例：20元的有4张，50元的有三张，这样的话去凑120元，按照我的想法，因为前面可以凑够80元，所以50的我只会选一张，剩下的70前面一定可以，但是事实上并不可以，OK，说服自己很舒服
于是正解：首先我们发现查安生错误的原因就是50和500需要多少张，为什么这两者特殊呢，因为对于别的数字，前面所有的数字都是这个数字的因子，唯独这两个数字前面的数字含有非因子，因此，对于每一个
数字，在我们找到最少选多少个之后，对于50,500，还要考虑要不要多选一张,其余的就不需要了。试着写一下
最原始想法代码：

#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<string.h>
#include<math.h>using namespace std;int t;
int num;
int tmp;
int a[13];
int c[13];
int sum[13];
int zhao[13] = {1,5,10,20,50,100,200,500,1000,2000};
int ans;
int l;
int fac[13];void init()
{fac[0] = 1;for(int i=1; i<=10; i++)fac[i] = fac[i-1]*2;
}int main()
{init();scanf("%d", &t);while( t-- ){scanf("%d", &num);ans = -1;for(int i=0; i<10; i++){scanf("%d", &a[i]);if(i == 0) sum[i] = a[i]*zhao[i];else sum[i] = sum[i-1]+a[i]*zhao[i];if(sum[i] <= num)l = i+1;}for(int i=fac[l]-3; i<=1023; i++){int ttmp = i;tmp = num;int res = 0;for(int j=9; j>=0; j--){if(!(ttmp>>j)&1) continue;if(zhao[j] > tmp){res = -1;break;}int wu = tmp-sum[j-1];int liu = max(1, (int)ceil(1.0*wu/zhao[j]));liu = min(liu, a[j]);res += liu;tmp -= liu*zhao[j];}if(tmp != 0){res = -1;}if(res != -1){ans = res;break;}}printf("%d\n", ans);}return 0;
}

View Code

错一发代码：

#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<string.h>
#include<math.h>using namespace std;const int maxn = 13;int t;
int num;
int a[maxn];
int f[10] = {1,5,10,20,50,100,200,500,1000,2000};
int sum[13];
int ans;void init()
{ans = -1;
}void input()
{scanf("%d" , &num);for(int i=0; i<10; i++){scanf("%d" , &a[i]);if(i == 0)sum[i] = a[i]*f[i];elsesum[i] = sum[i-1]+a[i]*f[i];
//        printf("%d..%d..\n" , i , sum[i]);
    }
}void solve(int id, int rem , int res)
{
//    printf("%d..%d..%d..\n" , id , rem , res);if(id < 0){if(rem == 0){ans = max(ans , res);}return ;}int tmp = rem-sum[id-1];int ttmp = max(0,(int)ceil(1.00*tmp/f[id]));ttmp = min(ttmp , a[id]);   ///算出来选择多少张solve(id-1 , rem-f[id]*ttmp , res+ttmp);if(f[id]==50 || f[id]==500){ttmp++;if(ttmp <= a[id])solve(id-1 , rem-f[id]*ttmp , res+ttmp);}
}int main()
{scanf("%d" , &t);while( t-- ){init();input();solve(9,num,0);printf("%d\n" , ans);}return 0;
}

View Code

看题解上写的是转换成尽可能多的去掉大面值的，使得剩下的可以构成要求的数字，对于50与500，另外考虑下少去掉一张，与我写的尽可能少选择大面值的，多选择一张有什么不同之处吗

代码是没有什么问题的 应该是逻辑上的问题

先改成去掉写一下试试

为什么就过了呢 这个问题暂时挖坑

#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<string.h>
#include<math.h>using namespace std;const int maxn = 13;
const int inf = 10000000;int t;
int num;
int a[maxn];
int f[10] = {1,5,10,20,50,100,200,500,1000,2000};
int sum[13];
int ans;
int all;void init()
{all = 0;ans = 10000000;
}void input()
{scanf("%d" , &num);for(int i=0; i<10; i++){scanf("%d" , &a[i]);all += a[i];if(i == 0)sum[i] = a[i]*f[i];elsesum[i] = sum[i-1]+a[i]*f[i];}
}void solve(int id, int rem , int res)
{if(id < 0){if(rem == 0){ans = min(ans , res);}return ;}int tmp = a[id];tmp = min(tmp , rem/f[id]);tmp = max(0 , tmp);solve(id-1 , rem-tmp*f[id] , res+tmp);if(tmp){tmp--;solve(id-1 , rem-tmp*f[id] , res+tmp);}
}int main()
{scanf("%d" , &t);while( t-- ){init();input();solve(9,sum[9]-num,0);
//        printf("%d...\n" , ans);if(ans == 10000000)printf("-1\n");elseprintf("%d\n" , all-ans);}return 0;
}

 

 

转载于:.html