AtCoder Beginner Contest 414 D

https://atcoder.jp/contests/abc414/tasks/abc414_d

まず基地局を各家に設置します。そして、基地局をMまで減らします。そのとき、d離れた家を基地局がカバーすることにすると、電波の強度もdになります。複数の家をカバーする基地局にもう一つ家をカバーできるようにするときも同じように強度がd増すことになります。なので、隣の家同士の距離をソートして、必要な分だけ小さいほうから足せばよいです。

// Transmission Mission
#![allow(non_snake_case)]


//////////////////// 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 ////////////////////

fn read_input() -> (usize, Vec<i64>) {
    let v: Vec<usize> = read_vec();
    let M = v[1];
    let X: Vec<i64> = read_vec();
    (M, X)
}

fn F(M: usize, mut X: Vec<i64>) -> i64 {
    X.sort();
    let mut diffs: Vec<i64> = X.iter().zip(X.iter().skip(1)).
                                map(|(&x, &y)| y - x).collect();
    diffs.sort();
    diffs[..X.len()-M].iter().sum()
}

fn main() {
    let (M, X) = read_input();
    println!("{}", F(M, X))
}