結果
問題 | No.198 キャンディー・ボックス2 |
ユーザー |
|
提出日時 | 2020-07-09 18:43:45 |
言語 | Rust (1.83.0 + proconio) |
結果 |
AC
|
実行時間 | 2 ms / 1,000 ms |
コード長 | 1,771 bytes |
コンパイル時間 | 14,981 ms |
コンパイル使用メモリ | 379,132 KB |
実行使用メモリ | 5,248 KB |
最終ジャッジ日時 | 2024-10-07 23:17:23 |
合計ジャッジ時間 | 14,338 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 26 |
ソースコード
use std::cmp::min; fn calc(boxes: &Vec<usize>, base: usize) -> usize { boxes.iter() .map(|&val| if val > base { val - base } else { base - val }) .sum() } fn main() { let mut b = String::new(); std::io::stdin().read_line(&mut b).ok(); let b: usize = b.trim().parse().unwrap(); let mut n = String::new(); std::io::stdin().read_line(&mut n).ok(); let n: usize = n.trim().parse().unwrap(); let mut boxes: Vec<usize> = vec![0; n]; let mut lower: usize = 1_000_000_000; let mut upper: usize = b as usize; for i in 0..n { let mut c = String::new(); std::io::stdin().read_line(&mut c).ok(); let val: usize = c.trim().parse().unwrap(); boxes[i] = val; lower = min(lower, val); upper += val; } upper /= n as usize; while upper - lower > 3 { let lmiddle = (2*lower + upper) / 3; let rmiddle = (lower + 2*upper) / 3; let minidx: usize = vec![lower, lmiddle, rmiddle, upper].iter() .map(|val| calc(&boxes, *val)) .enumerate() .min_by_key(|pair| pair.1) .map(|pair| pair.0) .unwrap() ; match minidx { 0 => { upper = lmiddle; }, 1 => { upper = rmiddle; }, 2 => { lower = lmiddle; }, _ => { lower = rmiddle; }, } } let lmiddle = (2*lower + upper) / 3; let rmiddle = (lower + 2*upper) / 3; let targets: Vec<usize> = vec![lower, lmiddle, rmiddle, upper]; let minidx: usize = targets.iter() .map(|val| calc(&boxes, *val)) .enumerate() .min_by_key(|pair| pair.1) .map(|pair| pair.0) .unwrap() ; println!("{}", calc(&boxes, targets[minidx])); }