SRM568 Div2 Medium "BallsSeparating"
問題
http://community.topcoder.com/stat?c=problem_statement&pm=12398
訳
0~N-1と番号が振られたN個の箱がある。
箱iには赤いボールがred[i]個、緑色のボールがgreen[i]個、青いボールがblue[i]個入っている。
1つの箱には1種類の色のボールしか入っていないようにしたい。
ある箱のボール1つを他の箱に移す事を1回の動作とすると、
最小何回の動作で作業が完了するかを返せ。
色をわけることが無理なら-1を返せ。
制約
1 <= N <= 50
1 <= red[i], green[i], blue[i] ( 0 <= i < N ) <= 10^6
考えた事
まず箱が最低でも3つないと無理。
あとはそれぞれの色を集める箱を決めて動作回数をシミュレートする。
ソースコード
class BallsSeparating { public: int minOperations(vector <int> red, vector <int> green, vector <int> blue) { int boxNum = red.size(); // 3箱未満はダメ if( boxNum < 3 ){ return -1; } // 箱の一番多く入っている色の数と // 箱を一色にする最小の操作数を取得する int maxColorNum[ 50 ]; int best = 0; for( int i = 0; i < boxNum; i++ ){ int s = red[ i ] + green[ i ] + blue[ i ]; int m = max( red[ i ], green[ i ] ); m = max( m, blue[ i ] ); best += s - m; maxColorNum[ i ] = m; } // 赤・緑・青の入れる箱を3箱決める // ベストからの差が一番少ないものに決定する int dif = INT_MAX; for( int r = 0; r < boxNum; r++ ){ for( int g = 0; g < boxNum; g++ ){ for( int b = 0; b < boxNum; b++ ){ if( r == g || g == b || b == r ){ continue; } int temp = 0; temp += maxColorNum[ r ] - red[ r ]; temp += maxColorNum[ g ] - green[ g ]; temp += maxColorNum[ b ] - blue[ b ]; dif = min( dif, temp ); } } } return best + dif; } };