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