水色プログラミング

競プロで解いた問題の記録,ゲーム制作の進捗など...

AtCoder Regular Contest 101:C - Candles

問題

N 本のろうそくが x 軸上に並んでいて,K 本のろうそくをつけたい.最初,座標 0 にいるとき,移動するための最小コストはいくつか求める問題.

解法

x 座標が正のろうそくを i 本,負のろうそくを N - i 本つけると考えて,0 <= i <= N 全てに対して計算する.その中で min を取ったものが答え.O(N).

解答

Submission #3073730 - AtCoder Regular Contest 101

f:id:babcs2035:20180825225621p:plain

gist.github.com