PAT甲级1068 Find More Coins (30分)（贪心+哈希表+堆栈）

题目描述

样例

Sample Input 1:
8 9
5 9 8 7 2 3 4 1
Sample Output 1:
1 3 5
Sample Input 2:
4 8
7 2 4 3
Sample Output 2:
No Solution

解题思路

1、由于要输出尽可能小的序列（如果序列存在），所以使用贪心的思路每步尽可能多的选取小面值硬币。
2、题目中说明需支付的金额不超过100， 因此只需利用哈希表统计面额不超过100的硬币个数。
3、堆栈保存已选择的硬币，按照题目要求设计入栈和出栈策略。

AC代码

#include <iostream>
#include <cstdio>
#include <stack>

using namespace std;
int coins[101];
int result[101];
int index = 0;

int main()
{
	int n, pay, tem, sum = 0;
	stack<int> sstack;
	cin >> n >> pay;
	for (int i = 0; i < n; i++)
	{
		cin >> tem;
		if (tem <= 100)
			coins[tem]++;
	}
	for (int i = 1; i <= pay; i++)
	{
		if (coins[i] == 0)
			continue;
		if ((pay - sum) % i == 0 && coins[i] >= (pay - sum) / i)
		{
			for (int j = 0; j < pay / i; j++)
				sstack.push(i);
			sum = pay;
			break;
		}
		else
		{
			for (int j = 0; pay - sum - i > i && j < coins[i]; j++)
			{
				sum += i;
				sstack.push(i);
			}
			if (pay - sum - i <= i)
			{
				if (coins[pay - sum] > 0)
				{
					sstack.push(pay - sum);
					sum = pay;
					break;
				}
				else
				{
					if (sstack.empty())
						break;
					i = sstack.top();
					sum -= i;
					sstack.pop();
				}
			}
		}
	}

	if (sum == pay)
	{
		while (!sstack.empty())
		{
			result[index++] = sstack.top();
			sstack.pop();
		}
		for (int i = index - 1; i >= 0; i--)
		{
			printf("%d", result[i]);
			if (i > 0)
				printf(" ");
		}
	}
	else
		printf("No Solution");

	return 0;
}