Q102: Ecological Bin Packing

有3个桶子用来装回收的玻璃瓶，玻璃瓶的颜色有三种：棕色（Brown）、绿色（Green）、透明色（Clear）。在这个问题里我们会告诉你每个桶子里的玻璃瓶的颜色及数量，现在要搬移桶子里的玻璃瓶使得最后每个桶子里都只有单一颜色的玻璃瓶，以方便回收。你的任务就是要算出最小搬移的瓶子数。你可以假设每个桶子的容量无限大，并且总共搬移的瓶子数不会超过2³¹。

Input

每笔测试资料一行，每行有9个整数.前3个代表第1个桶子里Brown, Green, Clear颜色的瓶子数。接下来的3个数代表 第2个桶子里Brown, Green, Clear颜色的瓶子数。最后的3个数代表第3个桶子里Brown, Green, Clear颜色的瓶子数。

例如：10 15 20 30 12 8 15 8 31 
表示有20个Clear色的玻璃瓶在第1个桶子里，12个Green色的玻璃瓶在第2个桶子里，15个Brown色的玻璃瓶在第3个桶子里。

Output

对每一笔测试资料，输出3个桶子内最后存放之玻璃瓶颜色，以及最小搬移的瓶子数。请以大写的'G'、 'B'、 'C' 分別代表绿色（Green）、棕色（Brown）、透明色（Clear）。

例如：BCG 30
代表最后搬移的结果第1个桶子内的玻璃瓶颜色为Brown，第2个桶子内的玻璃瓶颜色为Clear，第3个桶子内的玻璃瓶颜色为Green.并且总共搬移了30个玻璃瓶。

如果最小搬移瓶子数有一组以上的组合，请输出字典顺序最小的那一组答案。

Sample input

1 2 3 4 5 6 7 8 9
5 10 5 20 10 5 10 20 10

Sample Output

BCG 30
CBG 50

简体中文由Lucky貓的 UVA（ACM）園地转换。

原题：http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&category=3&problem=38&mosmsg=Submission+received+with+ID+12862920

又是一道水题，暴力破解。

#ifndef ONLINE_JUDGE
#pragma warning(disable : 4996)
#endif
#include <iostream>
#include <algorithm>
#include <string>
using namespace std;

typedef long long LL;

struct Bucket
{
	LL B;
	LL G;
	LL C;
};

Bucket b[3];
string cmd = "BCG";

LL count(const char& c, const Bucket& b)
{
	switch (c)
	{
	case 'B':
		return b.C + b.G;
	case 'G':
		return b.C + b.B;
	case 'C':
		return b.G + b.B;
	default:
		break;
	}
}

LL min_bottles;

LL solve(const string& cmd)
{
	LL result = 0;
	for (int i = 0; i < 3; ++i)
	{
		result += count(cmd[i], b[i]);
	}

	return result;
}

void initAll(string* all)
{
	int i = 0;
	all[i] = cmd;
	while (next_permutation(cmd.begin(), cmd.end()))
	{
		++i;
		all[i] = cmd;
	}
}

///////////////////////////SubMain//////////////////////////////////
int main(int argc, char *argv[])
{
#ifndef ONLINE_JUDGE
	freopen("in.txt", "r", stdin);
	freopen("out.txt", "w", stdout);
#endif
	string all[6];
	initAll(all);
	
	while (cin >> b[0].B >> b[0].G >> b[0].C >> b[1].B >> b[1].G >> b[1].C >> b[2].B >> b[2].G >> b[2].C)
	{
		min_bottles = solve(all[0]);
		int index = 0;
		for (int i = 1; i < 6; ++i)
		{
			int n = solve(all[i]);
			if (n < min_bottles)
			{
				min_bottles = n;
				index = i;
			}
		}
		cout << all[index] << ' ' << min_bottles << endl;
	}
#ifndef ONLINE_JUDGE
	fclose(stdin);
	fclose(stdout);
	// system("out.txt");
#endif
	return 0;
}
///////////////////////////End Sub//////////////////////////////////

 知识共享署名-非商业性使用-相同方式共享：码农场 » UVa Q102: Ecological Bin Packing