WARush

SRMの結果とか、解けた問題のコードを書いていきます

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;
  }

};