Tester解：F - Walnuts in Xmas Lease
投稿日： 更新日:
解説
より最大値を大きくするのではなく、最小値をまで大きくするのが適切であることが分かります。
二分探索を使って最小値を以上にできるかを探索します。最小値を以上にするには未満のに対し、だけ加える必要があります。この総和が以下であれば可能、そうでなければ不可能となります。
をの最大値とすると、計算量はです。
実装
use proconio::*;
fn main() {
input! {
n: usize,
w: i64,
a: [i64; n],
}
let f = |mi: i64| {
let mut sum = 0;
for i in 0..n {
sum += (mi - a[i]).max(0);
}
sum <= w
};
let mut ok = 0;
let mut ng = a.iter().max().unwrap() + 1;
while ng - ok > 1 {
let mid = (ok+ng)/2;
if f(mid) {
ok = mid;
} else {
ng = mid;
}
}
println!("{}", a.iter().max().unwrap() - ok);
}