3522441_tle.cc

北大大牛代码 1240道题的原代码 超级权威

#include <stdio.h>
#include <string.h>
#include <queue>
#include <algorithm>

using namespace std;

int num[4], c;
int value[] = {25, 10, 5, 1};

struct node
{
	int cnt[4];
	int total;

	void init()
	{
		total = 0;
		memset(cnt, 0, sizeof(cnt));
	}
};

queue <node> que;

node solve()
{
	node t, s;
	int i;

	while (!que.empty())
	{
		que.pop();
	}
	t.init();
	que.push(t);
	while (!que.empty())
	{
		t = que.front();
		que.pop();
		for (i = 0; i < 4; i++)
		{
			if (t.cnt[i] == num[i] || t.total + value[i] > c)
			{
				continue;
			}
			s = t;
			s.cnt[i]++;
			s.total += value[i];
			if (s.total == c)
			{
				return s;
			}
			que.push(s);
		}
	}
	return (node) {{0, 0, 0, 0}, -1};
}

int main()
{
	int i, t;

	while (1)
	{
		t = 0;
		for (i = 0; i < 4; i++)
		{
			scanf("%d", &num[i]);
			t += num[i];
		}
		scanf("%d", &c);
		if (c + t == 0)
		{
			break;
		}
		node ret = solve();
		if (ret.total == -1)
		{
			puts("Cannot dispense the desired amount.");
		}
		else
		{
			printf("Dispense %d quarters, %d dimes, %d nickels, and %d pennies.\n", ret.cnt[0], ret.cnt[1], ret.cnt[2], ret.cnt[3]);
		}
	}
	return 0;
}