[UVA][greedy] 11264 - Coin Collector
Problem E
Coin Collector
Input: Standard Input
Output: Standard Output
Our dear Sultan is visiting a country where there are n different types of coin. He wants to collect as many different types of coin as you can. Now if he wants to withdraw X amount of money from a Bank, the Bank will give him this money using following algorithm.
withdraw(X){
if( X == 0) return;
Let Y be the highest valued coin that does not exceed X.
Give the customer Y valued coin.
withdraw(X-Y);
}
Now Sultan can withdraw any amount of money from the Bank. He should maximize the number of different coins that he can collect in a single withdrawal.
Input:
First line of the input contains T the number of test cases. Each of the test cases starts with n (1≤n≤1000), the number of different types of coin. Next line contains n integers C1, C2, ... , Cn the value of each coin type. C1<C2<C3< … <Cn<1000000000. C1 equals to 1.
Output:
For each test case output one line denoting the maximum number of coins that Sultan can collect in a single withdrawal. He can withdraw infinite amount of money from the Bank.
|
Sample Input |
Sample Output |
|
2 6 1 2 4 8 16 32 6 1 3 6 8 15 20
|
6 4
|
Problemsetter: Abdullah Al Mahmud
Special Thanks To: Mohammad Mahmudur Rahman
一般常用的找錢方式，先找最大幣值的鈔票去找，現在要求找到最多不同種的硬幣。
題目解法：
原本想說窮舉一下，但這樣會跑太慢。
那麼轉換一下思路，因此當我們讀到 1 3 6 時，我們可以知道 10 元可以換到 3 種不同。
但是如果是 1 3 6 8 時，6 這種幣值的硬幣會(1+1+6 = 8)可能會消失，最多是 1 3 8 時。
在考慮 1 3 6 的可換不同種個數時，不會因為後面的幣值受影響。
而在會被換掉的情況，先把最大幣值的消去。
基於這幾種原則，進行 greedy。
#include <stdio.h>
int main() {
int testcase, n, C[1005];
int i, j;
scanf("%d", &testcase);
while(testcase--) {
scanf("%d", &n);
for(i = 0; i < n; i++)
scanf("%d", &C[i]);
long long sum = 0;
int ret = 0;
int stk[1005], stkIdx = -1;
for(i = 0; i < n; i++) {
while(sum >= C[i])
sum -= stk[stkIdx], stkIdx--;
stk[++stkIdx] = C[i];
sum += C[i];
if(stkIdx > ret)
ret = stkIdx;
}
printf("%d\n", ret+1);
}
return 0;
}