WARush

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

SRM582 Div1 Easy "SpaceWarDiv1"

問題

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

魔法少女はマジカルパワーを生まれ持った女の子である。地球を守るため、彼女たちは今日も戦う。宇宙からの敵は今まさに地球を侵略しようとしており、魔法少女たちはそれに立ち向かっている。

あなたは魔法少女のステータスであるint magicalGirlStrengthが与えられる。magicalGirlStrength[i]はi番目の少女の強さを表す。あなたは敵のステータスをであるint enemyStrengthとint[] enemyCountが与えられる。enemyStrenth[i]の強さを持った敵が、enemyCount[i]だけ出現している事を表す。

各魔法少女は常に1対1で敵と戦っている。魔法少女は敵の強さ以上の強さを持っている場合、その敵に打ち勝つ事が出来る。

戦いが始まるとき、彼女らの疲労度は0である。彼女らは敵を倒すたびに、疲労度が1増加してしまう。

魔法少女たちの目標は全ての敵を倒す事である。それは、各敵は誰か1人の魔法少女によって打ち負かされなければならない。さらに、魔法少女たちは、戦いが終わった後の、最大の疲労度を最小化したい。

全ての敵を倒す事が出来なければ-1を返せ。そうでなければ、最小化した最大の疲労度を返せ。

制約

1 <= 魔法少女の数 <= 50
1 <= 魔法少女の強さ <= 10000
1 <= 敵の強さの種類 <= 50
1 <= 敵の強さ <= 10000
1 <= 敵の各強さのその出現数 <= 10^14



考えた事

敵の数がくっそ多いから、この疲労度でいけるかな~つって2分探索していく。



ソースコード

class SpaceWarDiv1 {
public:
    long long minimalFatigue(vector <int> mgs, vector <int> es, vector<long long> ec){
        // 強さを降順にソート
        int N = mgs.size();
        sort( mgs.begin(), mgs.end(), greater<int>() );
        int M = es.size();
        for( int i = 0; i < M; i++ ){
            for( int j = 0; j < M - 1; j++ ){
                if( es[j] < es[j+1] ){
                    swap( es[j], es[j+1] );
                    swap( ec[j], ec[j+1] );
                }
            }
        }

        // めっさ強い敵がいたら地球滅亡
        if( mgs[0] < es[0] ) return -1LL;

        // 敵の数の総和をだしておく
        for( int i = 1; i < M; i++ ){
            ec[i] += ec[i-1];
        }

        // 2分探索
        long long h = ec[M-1];
        long long l = 1;
        while( l <= h ){
            long long m = (h + l) / 2; // 疲労度mで殲滅できないかな~
            bool ok = false;
            long long cnt = 0;
            for( int i = 0; i < N; i++ ){
                // 敵の強さを出す
                int eid = 0;
                while( ec[eid] <= cnt ){
                    eid++;
                }
                // 敵が魔法少女より強い
                if( mgs[i] < es[eid] ) break;

                // 敵をmだけ討伐
                cnt += m;

                // 敵を全て倒した
                if( ec[M-1] <= cnt ){
                    ok = true;
                    break;
                }
            }

            if( ok ){
                h = m - 1;
            }else{
                l = m + 1;
            }
        }

        return l;
    }
};