WARush

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

SRM681 Div1 Easy "FleetFunding"

解法

宇宙船を作る数を決め打ちする。
するとどうだろう、ワークショップを貪欲に使用することが出来る。
今、パーツpを作りたいと思った時、パーツを作ることができ(a[i] <= p <= b[i])、かつ期限が一番最初に切れてしまう(min(b[i]))なワークショップiを優先的に使用していくのがベスト。

決め打ちの数はにぶたんで。

ソースコード

// ワークショップをクラスに
class W {
public:
    int num;
    int L;
    int R;

    W (int _num, int _L, int _R) {
        num = _num;
        L = _L;
        R = _R;
    }

    // 最後のパーツの昇順でソートされるようにする
    bool operator< (const W& other) const {
        if (R < other.R) {
            return true;
        } else {
            return false;
        }
    }
    bool operator> (const W& other) const {
        if (R > other.R) {
            return true;
        } else {
            return false;
        }
    }
};

int N;
int M;
vector<int> K;
vector<int> A;
vector<int> B;

class FleetFunding {
    public:
    int maxShips(int m, vector<int> k, vector<int> a, vector<int> b) {
        N = k.size();
        M = m;
        K = k;
        A = a;
        B = b;

        // にぶたんで機数を決め打ち
        int L = 0;
        int R = 1000000 * 50 + 1;
        while (L + 1 < R) {
            int mi = (L + R) / 2;
            if (solve(mi)) {
                L = mi;
            } else {
                R = mi;
            }
        }
        return L;
    }

    bool solve(int need) {
        vector<W> ws;
        for (int i = 0; i < N; i++) {
            ws.push_back(W(K[i], A[i], B[i]));
        }
        sort(ws.begin(), ws.end());

        for (int p = 1; p <= M; p++) {
            int rem = need;
            for (int i = 0; i < N; i++) {
                W w = ws[i];
                if (ws[i].R < p || p < ws[i].L) continue;
                if (rem < w.num) {
                    // 余力アリ
                    ws[i].num -= rem;
                    rem = 0;
                } else {
                    // 余力ナシ
                    rem -= w.num;
                    ws[i].num = 0;
                }
            }
            if (rem != 0) return false;
        }

        return true;
    }
};