SRM568 Div1 Easy - BallsSeparating

問題

n個の箱があり、i番目の箱には赤緑青のボールがそれぞれr,g,b[i]個入っている
ある箱からある色のボールを取り出し違う箱に入れるにはコストが1かかる
それぞれの箱に入っているボールの色の種類を1以下にするためにかかるコストの最小値を求めよ

1 <= n <= 50
1 <= r, g, b[i] <= 10^6

解法

赤緑青それぞれのボールを集める箱(i,j,kとする)を全探索する
箱i,j,kに関しては対応しない2種類の色のボールの個数だけコストがかかる
それ以外の箱については最も個数が多い色のボールだけ残して、その他の2色のボールだけ移動すればいい

class BallsSeparating {
public:
	int minOperations(vector<int> r, vector<int> g, vector<int> b) {
		int n = r.size(), res = 1<<30;
		if (n<3) return -1;
		rep(i,n) rep(j,n) rep(k,n) if (i!=j && j!=k && k!=i) {
			int s = 0;
			rep(x,n) {
				if (x==i) s += g[x]+b[x];
				else if (x==j) s += b[x]+r[x];
				else if (x==k) s += r[x]+g[x];
				else s += r[x]+g[x]+b[x] - max(r[x],max(g[x],b[x]));
			}
			chmin(res,s);
		}
		return res;
	}
};

https://community.topcoder.com/stat?c=problem_statement&pm=12398&rd=15488