UVa 11264 Coin Collector （选硬币&贪心好题）

UVa 11264 Coin Collector （选硬币&贪心好题）2014-07-24

11264 - Coin Collector

Time limit: 3.000 seconds

http://uva.onlinejudge.org/index.php？option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=2231

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

思路：

1. 你肯定注意到了，面值最大的硬币c[n-1]必须要选。（反证：如果花了sum元却没有选中它，可知sum<c[n-1]，于是用m+c[n-1]元去兑换可以得到一个更优解。）

2. 贪心的关键：假设S（i）是c[1]…c[i] 中那些被选中的货币的面值的和。那么一定有 S（i） < c[i+1]。

3. 所以可以构造一个这样的序列出来。按照2中所说，如果有 S（i-1） < c[i]且S（i） =S（i-1）+c[i]<c[i+1]，那么c[i]将被选中。

完整代码：

/*0.015s*/#include<cstdio>int c[1005];int main（）{int t, n, i, sum, count;scanf（"%d", &t）;while （t--）{scanf（"%d", &n）;for （i = 0; i < n; ++i）scanf（"%d", &c[i]）;if （n <= 2） printf（"%d
", n）;else{sum = c[0], count = 2;///先把最后一个算上for （i = 1; i < n - 1; ++i）if （sum < c[i] && sum + c[i] < c[i + 1]）sum += c[i], ++count;printf（"%d
", count）;}}return 0;}

作者署名：csdn博客 synapse7