問題
http://community.topcoder.com/stat?c=problem_statement&pm=12398&rd=15488
解き方
基本的に貪欲法だが、少なくとも各色ごとに１つは箱を用意する必要があるので
各色ひとつずつ箱を決めた場合について、貪欲法で解く。
コード
class BallsSeparating {
public: int minOperations(vector<int> red, vector<int> green, vector<int> blue) {
int n=red.size();
int r=0,g=0,b=0;
FORE(i,0,n){
if(red[i]>0)r=1;
if(green[i]>0)g=1;
if(blue[i]>0)b=1;
}
if(r+g+b>n)return -1;
int ret=1e+9;
FORE(i,0,n)FORE(j,0,n)FORE(k,0,n)if(i!=j && j!=k && k!=i){
int cost=0;
FORE(l,0,n){
if(l==i)cost+=green[l]+blue[l];
else if(l==j)cost+=red[l]+blue[l];
else if(l==k)cost+=red[l]+green[l];
else{
cost+=red[l]+green[l]+blue[l]-max(red[l],max(green[l],blue[l]));
}
}
ret=min(ret,cost);
}
return ret;
}
};
public: int minOperations(vector<int> red, vector<int> green, vector<int> blue) {
int n=red.size();
int r=0,g=0,b=0;
FORE(i,0,n){
if(red[i]>0)r=1;
if(green[i]>0)g=1;
if(blue[i]>0)b=1;
}
if(r+g+b>n)return -1;
int ret=1e+9;
FORE(i,0,n)FORE(j,0,n)FORE(k,0,n)if(i!=j && j!=k && k!=i){
int cost=0;
FORE(l,0,n){
if(l==i)cost+=green[l]+blue[l];
else if(l==j)cost+=red[l]+blue[l];
else if(l==k)cost+=red[l]+green[l];
else{
cost+=red[l]+green[l]+blue[l]-max(red[l],max(green[l],blue[l]));
}
}
ret=min(ret,cost);
}
return ret;
}
};