24/12/16 23:23:08.71 pEIdxfnL.net
>>11
重さ(w)があるのに価値(v)がないものを取り除いている
Rustで書くとこんな感じ
軽い順で入力が入ってくる状況で
scanで今まで来た価値(v)の最大値を求めていて
filterでその自分より前の最大値より価値(v)が大きいものだけを取り出している
fn sieve(sorted_input: impl IntoIterator<Item = (u32, u32)>) -> impl Iterator<Item = (u32, u32)> {
sorted_input
.into_iter()
.scan(0, |v_max, (w, v)| {
let pre_v_max = *v_max;
*v_max = v.max(pre_v_max);
Some((w, v, pre_v_max))
})
.filter_map(|(w, v, pre_v_max)| {
(v > pre_v_max)
.then_some((w, v))
})
}