問題概要
$p_1$から$p_m$の$m$個のパーツからなる宇宙船がある.
$n$個のパーツ売り場があり, それぞれの売り場では閉区間$[a, b]$の添字のパーツが売られている. 各売り場で買えるパーツの数は$k$個までである.
作れる宇宙船の数の最大値を求めなさい.
制約
- $1 \leq n \leq 50$
- $1 \leq m \leq 10^5$
- $1 \leq k \leq 10^6$
- $1 \leq a \leq b \leq m$
考察
(各パーツの個数の)最小値の最大化なので二分探索.
あとは判定パートの実装だけど, ここでつまづいた.
判定
区間スケジューリングっぽく$b$が早いものから処理すれば良さそうな気持ちになる.
売り場を$b$でソートして処理すればいいと思ったけど, どのパーツをどれぐらい買えばいいのかがわからず…
ここで思考が停止してしまった(よくない).
どのパーツをどれぐらい買えばいいのかわからないんだったら, パーツごとに考えればいい.
$p_1$から順番に買えるかどうかを考える.
売り場を前からなめて欲しいパーツが売ってたら, 超えない程度に買えるだけ買うのを繰り返す.
途中で足りなくなったらfalseを返す.
$p_1$から$p_m$まで全部買えたらtrueを返す.
計算量
二分探索が$O(\log nk)$, 判定パートが$O(nm)$なので, 全体で$O(nm\log nk)$.
実装
閉区間が嫌だったので, なんとなく半開区間にした.
ソートが複雑になることを危惧してshop構造体を作ったけど, これだとtupleでよかった.
難易度が上がるにつれてコードとにらめっこする時間は増えるだろうし, 多少の実装量を犠牲に可読性あげるのに慣れとくのはいいことなのかも.
提出コード(C++🔆)
struct FleetFunding {
struct shop {
int k, a, b;
shop() : k(0), a(0), b(0) {}
shop(int k, int a, int b) : k(k), a(a), b(b) {}
bool operator<(const shop &s) const {
return b < s.b;
}
};
bool check(int mid, int m, vector<shop> shops) {
REP(i, m) {
int bought = 0;
EACH(s, shops) {
if (s.k <= 0 || s.a > i || s.b <= i) continue;
int need = mid - bought;
if (need >= s.k) {
bought += s.k;
s.k = 0;
} else {
bought += need;
s.k -= need;
}
if (bought >= mid) break;
}
if (bought < mid) return false;
}
return true;
}
int maxShips(int m, vector<int> k, vector<int> a, vector<int> b) {
int n = (int)k.size();
vector<shop> shops;
REP(i, n) shops.emplace_back(shop(k[i], a[i] - 1, b[i])); // [a, b)
SORT(shops);
{
ll ok = 0, ng = INT_MAX;
while (abs(ok - ng) > 1) {
ll mid = (ok + ng) / 2;
if (check(mid, m, shops)) {
ok = mid;
} else {
ng = mid;
}
}
return ok;
}
}
};