SRM629 Div1 Easy "RectangleCovering"

問題

TopCoder Statistics - Problem Statement

考えたこと

穴の辺上に合わせるようにボードを乗っけることはできないと・・

つまりどういう事だってばよ

こう、縦横をテクニカルに埋めていって最小にする、みたいな事はできなそうだな！（フィーリング）

縦なら縦、横なら横、って感じで埋めてくしかなさそう。

辺の長いほうを埋めてくほうが有利かな？（フィーリング）

・・・最後のサンプル通らない

やっぱり縦と横両方やろ

通った！Submit!

撃　墜

あ、穴を埋めるのはちょうどでいいやん・・・辺上とか関係ないやん・・・

事後

今回通ったとしても、フィーリングでやるのはちょっとまずいよねぇ。考えが合ってるか多少なりとも証明するようにしないと・・・

ソースコード

class RectangleCovering {
public:

    int minimumNumber(int holeH, int holeW, vector <int> boardH, vector <int> boardW) {
        int res = min(solve(holeH, holeW, boardH, boardW), solve(holeW, holeH, boardH, boardW));
        if (res == 100) return -1;
        return res;
    }

    int solve(int a, int b, vector <int> boardH, vector <int> boardW) {
        int n = boardH.size();
        vector<int> bs;
        for (int i = 0; i < n; i++) {
            int c1 = 0;
            int c2 = 0;

            if (a < boardH[i]) {
                c1 = boardW[i];
            }
            if (a < boardW[i]) {
                c2 = boardH[i];
            }
            bs.push_back(max(c1, c2));
        }

        sort(bs.begin(), bs.end());
        reverse(bs.begin(), bs.end());

        int sum = 0;
        for (int i = 0; i <= n; i++) {
            if (sum >= b) return i;
            if (i == n) break;
            sum += bs[i];
        }
        return 100;
    }
};