AtCoder Beginner Contest 415 D

https://atcoder.jp/contests/abc415/tasks/abc415_d

今の瓶の数をnとすると、Aがn以上でA-Bが小さいショップを選べばよいです。なので、BTreeSetでA-B順にショップを並べて、別にAで並べたショップVecを持っておき、ショップのAがnを超えたらBTreeSetとVecから同時に消せばよいです。

// Get Many Stickers
#![allow(non_snake_case)]

use std::collections::BTreeSet;


//////////////////// library ////////////////////

fn read<T: std::str::FromStr>() -> T {
    let mut line = String::new();
    std::io::stdin().read_line(&mut line).ok();
    line.trim().parse().ok().unwrap()
}

fn read_vec<T: std::str::FromStr>() -> Vec<T> {
    read::<String>().split_whitespace()
            .map(|e| e.parse().ok().unwrap()).collect()
}


//////////////////// process ////////////////////

type Exc = (i64, i64);

fn read_exc() -> Exc {
    let v: Vec<i64> = read_vec();
    (v[0], v[1])
}

fn read_input() -> (i64, Vec<Exc>) {
    let v: Vec<i64> = read_vec();
    let (N, M) = (v[0], v[1] as i32);
    let exchanges: Vec<Exc> = (0..M).map(|_| read_exc()).collect();
    (N, exchanges)
}

fn F(N: i64, exchanges: Vec<Exc>) -> i64 {
    let mut v: Vec<(i64, i64)> = exchanges.iter().
                                    map(|&(A, B)| (A-B, A)).collect();
    v.sort_by_key(|&(_, A)| A);
    let mut tree: BTreeSet<(i64, i64)> = v.iter().cloned().collect();
    let mut counter: i64 = 0;
    let mut n = N;
    while !tree.is_empty() {
        let mut i = 0;
        for &(_, A) in v.iter().rev() {
            if A <= n {
                break
            }
            i += 1
        }
        for _ in 0..i {
            let e = v.pop().unwrap();
            tree.remove(&e);
        }
        
        if let Some(&(d, A)) = tree.first() {
            let q = (n - A) / d + 1;
            counter += q;
            n -= q * d
        }
        else {
            break
        }
    }
    counter
}


fn main() {
    let (N, exchanges) = read_input();
    println!("{}", F(N, exchanges))
}