WARush

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

SRM586 Div2 Easy "TeamsSelection"

問題

http://community.topcoder.com/stat?c=problem_statement&pm=12696

男の子達がサッカーで遊ぼうとしている。N+2人の男の子がいて、この中で2人がキャプテンに選ばれている。キャプテンはN人を2つのチームにわけたい。便利のため、キャプテンを除く男の子を1からNと番号をつけることにする。

チームにわける方法は以下の通りである。最初は、1チーム目のキャプテンがチームに入れる人を一人選ぶ。それから2チーム目のキャプテンが、既に選ばれている人を除いた中から、チームに入れる人を一人選ぶ。それから1チーム目のキャプテンが同じことをする。そしてそれが続けられていく。選ばれていない人がいなくなるまで、これが続けられていく。

あなたはそれぞれN個の要素を持つ、int[] preference1とpreference2が与えられる。preference1[0]は1チーム目のキャプテンが最もよいプレイヤーだと評価している人の番号であり、preference1[1]は1チーム目のキャプテンが次によいプレイヤーだと評価している人の番号であり、それが続いていく。preference2は、同じように、2チーム目のキャプテンの評価の情報を表している。キャプテンは選手を貪欲に選んでいく。つまり、まだ選ばれてない人の中から、最も評価している選手を選んでいく。

Nの長さの文字列を返せ。i番目の文字は、i番目の選手が1チーム目に入るならば'1'、2チーム目に入るならば'2'とせよ。

制約

2 <= N <= 50



考えた事

やるだけ



ソースコード

class TeamsSelection {
public:
    string simulate(vector <int> p1, vector <int> p2){

        int n = p1.size();

        char res[55];
        bool use[55];
        memset( use, false, sizeof(use) );
        for( int i = 0; i < n; i++ ){
            int id = -1;
            for( int j = 0; j < n; j++ ){
                if( i % 2 == 0 ){
                    if( !use[p1[j]] ){
                        id = p1[j];
                        break;
                    }
                }else{
                    if( !use[p2[j]] ){
                        id = p2[j];
                        break;
                    }
                }
            }
            if( i % 2 == 0 ){
                res[id-1] = '1';
            }else{
                res[id-1] = '2';
            }
            use[id] = true;
        }


        string ans;
        for( int i = 0; i < n; i++ ){
            ans += res[i];
        }
        return ans;
    }
};