SRM 681 div1 easy: FleetFunding

問題

TopCoder Statistics - Problem Statement

解法

二分探索で答えを求めていきます。

ok(x) = (x 個の spaceship を作ることが出来るか？) とします。

b の小さいのから順にパーツを作っていくと, 後ろのパーツを作るのになるべく余裕をもたせられるようになり, 最適です。なんかこういうのは区間スケジューリング問題でよくあるパターンなので区間スケジューリングっぽかったらとりあえず(今回であれば) b の順にソートする, というのは考えたほうが良いですね。

ok 関数の詳しい実装なんですが, map を使いました。

map mp というのに, mp[i] = (種類 i のパーツをあといくつつくらなければならないか) というのを保持しておきます。

j 番目の workshop を考える時, a 〜 b の種類のパーツのうち作れるものがあれば前からどんどん作っていきます。a 以上で作れるパーツを探すときは, lower_bound を使えば良いです。また, mp[i] = 0 となったら, lower_bound するとき邪魔になるので i 番目の要素は erase しましょう。mp.erase(it++) とすると, イテレータは 1 つ先に進めながら, 指定したイテレータは消してくれるので嬉しいです(最近知った)。

bool ok(int x, int m, vi k, vi a, vi b) {
    int n = k.size();
    vector<pair<pii, int> > P(n);
    for (int i = 0; i < n; i++) P[i] = make_pair(pii(b[i], a[i]), k[i]);
    sort(P.begin(), P.end());
    map<int, int> mp;
    for (int i = 1; i <= m; i++) mp[i] = x;
    for (int i = 0; i < n; i++) {
        int A = P[i].first.second, B = P[i].first.first, K = P[i].second;
        auto it = mp.lower_bound(A);
        while (it != mp.end() && it->first <= B && K > 0) {
            int minus = min(K, it->second);
            it->second -= minus;
            if (it->second == 0) mp.erase(it++);
            else it++;
            K -= minus;
        }
    }
    return mp.empty();
}

class FleetFunding {
public:
    int maxShips(int m, vector <int> k, vector <int> a, vector <int> b) {
        int low = 0, high = 55*1000000;
        while (high-low > 1) {
            int med = (high+low)/2;
            if (ok(med, m, k, a, b)) low = med;
            else high = med;
        }
        return low;
    }
};