1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
|
use std::io::{BufRead};
/*
* The corresponding real-relaxed problem attains its cost minimum at
* position x when
*
* x + L(x)/(2N)
*
* is as close to the average of all the initial positions as
* possible. Here L is the function defined by
*
* L(x) = (num of initials < x) - (num of initials > x).
*
* We compute L and the average in linear time, and then the best
* *integer* approximation of x in linear time. In order to not have
* to thoroughly fuss about the error in the real-relaxed problem, we
* then check the two integer neighbors of that integer
* approximation.
*
* Equivalently, to avoid floating point computations, we look at
* when 2Nx + L(x) is as close as possible to 2S, where S is the sum
* of all initial positions.
*
*/
fn cost(positions: & [i64], dest: i64) -> i64 {
positions.into_iter().map(|x| ((x-dest).pow(2) + (x-dest).abs())/2).sum()
}
pub fn main() {
let mut stdin = std::io::stdin();
let mut handle = stdin.lock();
let input: String = {
let mut buf = String::new();
handle.read_line(&mut buf).unwrap();
String::from(buf.trim_end())
};
let positions: Vec<i64> = {
let mut tmp: Vec<i64> = input.split(',').map(|w| w.parse().expect("Malformed input")).collect();
(&mut tmp).sort();
tmp
};
let n: usize = positions.len();
let s: i64 = (& positions).into_iter().sum();
// FIXME: Should build this backwards instead, but whatever.
let l: Vec<i64> = {
let mut ret: Vec<i64> = Vec::with_capacity(n);
let mut pos: i64 = positions[0];
let mut dups: usize = (& positions[0..]).into_iter().take_while(|p| **p == pos).count();
ret.extend(std::iter::repeat(-(n as i64) + (dups as i64)).take(dups));
let mut i: usize = dups;
while i < (n as usize) {
pos = positions[i];
dups = (& positions[i..]).into_iter().take_while(|p| **p == pos).count();
ret.extend(std::iter::repeat((dups as i64) + ret[i-1]).take(dups));
i += dups;
}
ret
};
let best_relaxed_position: i64 = {
let mut ret = positions[0];
let mut best = i64::MAX;
for i in 0..n {
let err = (2*(n as i64)*positions[i] + l[i] - 2*s).abs();
if err < best {
ret = positions[i];
best = err;
}
}
ret
};
println!("Best relaxed position: {} (will therefore check {}, {}, {}).", best_relaxed_position, best_relaxed_position-1, best_relaxed_position, best_relaxed_position+1);
let best_cost = [-1, 0, 1].into_iter().map(|offset| cost(& positions, best_relaxed_position + offset)).min().unwrap();
println!("Minimal fuel cost: {}", best_cost);
}
|
