ABC137 D - Summer Vacation
問題
解法
どの仕事も1日で終わるので、もらえる金額が大きければ大きいほどよい。よってもらえる金額が大きい方から処理していく。もらえる金額が同じ仕事同士では、振込が早い仕事よりも遅い仕事の方が候補日が限られるので、遅い仕事から処理する。
ある仕事 i を引き受けるかどうかを決めるとき、M-a_i日目までに終わらせなければならない。1日目〜M-a_i日目の間でまだ仕事を入れていない日があれば、そこに仕事を入れる。もし埋まっていた場合、そこを埋めている仕事は必ず仕事i以上の給料の仕事なので、仕事iと入れ替えても総額は上がらない。よって仕事iを引き受けなくて良いことになる。
これらを繰り返していくことで最適解が得られる。
コード
use std::collections::BTreeSet; fn main() { let s = std::io::stdin(); let mut sc = Scanner { stdin: s.lock() }; let n: usize = sc.read(); let m: usize = sc.read(); let mut tasks = vec![]; for _ in 0..n { let days: usize = sc.read(); let value: u64 = sc.read(); tasks.push((value, days)); } tasks.sort(); tasks.reverse(); let mut remain = (0..(m + 1)).collect::<BTreeSet<_>>(); let mut ans = 0; for (value, days) in tasks.into_iter() { if m < days { continue; } let d = m - days; if let Some(&d) = remain.range(..(d + 1)).next_back() { remain.remove(&d); ans += value; } } println!("{}", ans); } pub struct Scanner<R> { stdin: R, } impl<R: std::io::Read> Scanner<R> { pub fn read<T: std::str::FromStr>(&mut self) -> T { use std::io::Read; let buf = self .stdin .by_ref() .bytes() .map(|b| b.unwrap()) .skip_while(|&b| b == b' ' || b == b'\n') .take_while(|&b| b != b' ' && b != b'\n') .collect::<Vec<_>>(); unsafe { std::str::from_utf8_unchecked(&buf) } .parse() .ok() .expect("Parse error.") } pub fn vec<T: std::str::FromStr>(&mut self, n: usize) -> Vec<T> { (0..n).map(|_| self.read()).collect() } pub fn chars(&mut self) -> Vec<char> { self.read::<String>().chars().collect() } }