Too Rich
Time Limit: 6000/3000 MS (Java/Others) Memory Limit: 262144/262144 K (Java/Others)
Total Submission(s): 245 Accepted Submission(s): 76
Problem Description
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 pdollars 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.
Input
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 ci means how many coins/banknotes in denominations of i dollars in your wallet.
1≤T≤20000
0≤p≤109
0≤ci≤100000
Output
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'.
Sample Input
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
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
Sample Output
9
-1
36
-1
36
Source
题意：博客吃回车，没办法。
就是说用尽量多的钞票组合成币值p，问最多用多少。
分析：
尽量用比值小的，如果先从小的开始，我们不知道小的币值能不能凑出当前所需钱数
所以从大的开始
可以发现，如果后面的钱数一共能凑出a,现在共需b，那么当前这个币值我们所需要凑出的就是（b-a），所需数量显然是max(ceil((b-a)/(当前的币值), 0)
然而，这并不是绝对的，固然，这个数量可以使后面的尽量多，但是诸如20，20，20，50这样的例子，假设b是50，那么因为a是60，导致错误，所以有可能会多用一张当前的钞票
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <deque>
#include <vector>
#include <queue>
#include <iostream>
#include <algorithm>
#include <map>
#include <set>
#include <ctime>
using namespace std;
typedef long long LL;
typedef double DB;
#define For(i, s, t) for(int i = (s); i <= (t); i++)
#define Ford(i, s, t) for(int i = (s); i >= (t); i--)
#define Rep(i, t) for(int i = (0); i < (t); i++)
#define Repn(i, t) for(int i = ((t)-1); i >= (0); i--)
#define rep(i, x, t) for(int i = (x); i < (t); i++)
#define MIT (2147483647)
#define INF (1000000001)
#define MLL (1000000000000000001LL)
#define sz(x) ((int) (x).size())
#define clr(x, y) memset(x, y, sizeof(x))
#define puf push_front
#define pub push_back
#define pof pop_front
#define pob pop_back
#define ft first
#define sd second
#define mk make_pair
inline void SetIO(string Name)
{
string Input = Name+".in",
Output = Name+".out";
freopen(Input.c_str(), "r", stdin),
freopen(Output.c_str(), "w", stdout);
} inline int Getint()
{
int Ret = ;
char Ch = ' ';
bool Flag = ;
while(!(Ch >= '' && Ch <= ''))
{
if(Ch == '-') Flag ^= ;
Ch = getchar();
}
while(Ch >= '' && Ch <= '')
{
Ret = Ret * + Ch - '';
Ch = getchar();
}
return Flag ? -Ret : Ret;
} const int N = , Money[] = {, , , , , , , , , , };
int p, Arr[N];
LL Sum[N];
int Ans; inline void Solve(); inline void Input()
{
int TestNumber = Getint();
while(TestNumber--)
{
p = Getint();
For(i, , ) Arr[i] = Getint();
Solve();
}
} inline void Search(int Last, int x, int Cnt)
{
if(Last < ) return;
if(x < )
{
if(!Last) Ans = max(Ans, Cnt);
return;
}
LL Rest = max(Last - Sum[x - ], 0LL);
int Number = Rest / Money[x];
if(Rest % Money[x]) Number++;
if(Number <= Arr[x])
Search(Last - 1LL * Number * Money[x], x - , Cnt + Number);
if(++Number <= Arr[x])
Search(Last - 1LL * Number * Money[x], x - , Cnt + Number);
} inline void Solve()
{
Sum[] = ;
For(i, , N) Sum[i] = Sum[i - ] + 1LL * Arr[i] * Money[i];
Ans = -;
Search(p, , );
printf("%d\n", Ans);
} int main()
{
#ifndef ONLINE_JUDGE
SetIO("");
#endif
Input();
//Solve();
return ;
}