ABC137 D - Summer Vacation

問題

atcoder.jp

解法

どの仕事も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()
    }
}