UVa 11264 Coin Collector (选硬币&贪心好题)

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]。（反证：若S(i)>=c[i+1]，那银行肯定要找给他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", 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\n", count);
		}
	}
	return 0;
}