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; } };