ABC471 C - Cookies and Greedy Takahashi

考え方

タイトルにある通り、貪欲法でよい。
つまり、以下の $2$ つのうち近い方を常に取ればよい。

• 自分より右にあるなかで最も座標が小さいもの
• 自分より左にあるなかで最も座標が大きいもの

これをやり続けると、自分より左右というのは座標の正負そのままになる。
つまり、このような $2$ つと思ってもよい。

• 正の座標のなかで最も座標が小さいもの
• 負の座標のなかで最も座標が大きいもの

実装方法はいくつかある。
deque や priority_queue を $2$ つ用いて食べたクッキーのデータを削除しながら解く方法もある。

以下では、ソートしてツーポインタ法で解く方法で解説する。

まず、全体をソートする。
そして、正の数と負の数の境界位置を探す（$0$ は適当にどちらかに入れる）。
これは、二分探索してもいいし、前から愚直に調べてもよい。
境界位置のすぐ左が a[l] 右が a[r] となるように l と r を用意する。

それから、a[l] と a[r] の近い方を食べる。
左がもうない場合か、右の方が近い場合は、以下の $3$ つを処理する。

• 結果に、今回の移動距離を足す
• 現在位置をクッキーの位置 a[r] に更新
• r を $1$ 増やす

逆の場合（等距離の場合を含む）は

• 結果に、今回の移動距離を足す
• 現在位置をクッキーの位置 a[l] に更新
• l を $1$ 減らす

最終的に l が $-1$ で r が $N$ になったら、クッキーを全部食べたのでおしまい。

計算量はソート部分が支配的で $O(N\log N)$。

入力例1での動作

入力を受け取る。

n: 4
a: {-1, -4, 2, -11}

配列をソートすると、

a: {-11, -4, -1, 2}

となる。

最初の正の数は a[3]=2 なので、$r=3$、$l=2$ とする。
また、現在位置は $0$、移動距離の合計は $0$ である。

以降は次のように進む。

$1$ 回目は左側を食べるので、l を $2$ から $1$ に減らす。
$2$ 回目も左側を食べるので、l を $1$ から $0$ に減らす。
このとき左右への距離がともに $3$ なので、座標の小さい左側の $-4$ を選ぶ。
$3$ 回目は右側を食べるので、r を $3$ から $4$ に増やす。
$4$ 回目は右側にクッキーが残っていないので左側を食べ、l を $0$ から $-1$ に減らす。

最後に $l=-1$, $r=4=N$ となり、全てのクッキーを回収した。
移動距離の合計は $23$ であり、これが答えである。

注意点

移動距離の合計は、int 型からはみ出る。
long long 型を用いること。

別解

番兵として、非常に遠いクッキーを左右に置いて、残り $2$ つになるまで続ける方法もある。
この場合、片方がなくなっている可能性を考慮しなくていい分、どちらを食べに行くかの判定が楽になる。

ただし、クッキーが存在する範囲の端から端への移動を妨害しないようにしなければならない。
つまり、番兵で入れる値の絶対値は $3\times 10^9+1$ 以上でなければならない。
すると、今度は int 型だとオーバーフローが発生する問題が発生し、long long 型が要求される。

このように、こちらはこちらで気を遣う点が多い。