2023-05-06 PAST #2 F を解いた
- PAST #2 F - タスクの消化 (第二回 アルゴリズム実技検定 F問題)
https://atcoder.jp/contests/past202004-open/tasks/past202004_f
- https://atcoder.jp/contests/past202004-open/submissions/41214293
- 貪欲法
- k 日目はその日に選択可能なもので未選択のもののうち最大のものを選べば良い
- BinaryHeap ないし BTreeSet で選択可能になったものを追加し、順次大きいものを取り出していけば良い
use std::collections::BinaryHeap;
use proconio::{input, marker::Usize1};
fn main() {
input! {
n: usize,
mut ab: [(Usize1, usize); n],
}
ab.sort();
let mut sum = 0_usize;
let mut index = 0_usize;
let mut pq = BinaryHeap::new();
for k in 0..n {
while index < n {
let (a, b) = ab[index];
if a <= k {
pq.push(b);
index += 1;
} else {
break;
}
}
sum += pq.pop().unwrap();
println!("{}", sum);
}
}
変な時間に目が覚めた。
今日のコミット。