問題
①箱がＮ個与えられる。
②箱には赤・緑・青のボールがランダムな数だけ入っている。
③それぞれの箱には１色のボールしか入らないようにボールを移動したとき、
ボールの最小移動回数を求める。
解き方
単純に考えると、各箱のうち最大のボールが入っている色を残せばよいことになる。
ただしボールの数によってはいずれかの色が選ばれない場合に
その色へ移動できないのでエラーとなってしまう。
そのため、各色ごとに入れる箱をあらかじめ１つ選んでおくことで防ぐことができる。
その選び方を全通り試して、
あとはすべての箱に対して最大の色だけ残すようにすればよい。
コード
class BallsSeparating {
public: int minOperations(vector<int> red, vector<int> green, vector<int> blue) {
int ans=160000000;
int n=red.size();
if(n<3)return -1;
FORE(i,0,n){
FORE(j,0,n){
if(i==j)continue;
FORE(k,0,n){
if(i==k||j==k)continue;
int cur=0;
cur+=(green[i]+blue[i]+red[j]+blue[j]+red[k]+green[k]);
FORE(l,0,n){
if(l!=i && l!=j && l!=k)
cur+=(red[l]+green[l]+blue[l]-max(red[l],max(green[l],blue[l])));
}
ans=min(ans,cur);
}
}
}
return ans;
}
};
public: int minOperations(vector<int> red, vector<int> green, vector<int> blue) {
int ans=160000000;
int n=red.size();
if(n<3)return -1;
FORE(i,0,n){
FORE(j,0,n){
if(i==j)continue;
FORE(k,0,n){
if(i==k||j==k)continue;
int cur=0;
cur+=(green[i]+blue[i]+red[j]+blue[j]+red[k]+green[k]);
FORE(l,0,n){
if(l!=i && l!=j && l!=k)
cur+=(red[l]+green[l]+blue[l]-max(red[l],max(green[l],blue[l])));
}
ans=min(ans,cur);
}
}
}
return ans;
}
};