F - Minimize Bounding Square 解説 by hirayuu_At
Slope Trickを使用した別解(雑です。後でしっかりしたものになるかもしれません。)
答えで二分探索して、「答えを \(a\) 以下にできるか?」を解きます。
また、x座標とy座標は独立に考えて何ら支障がないので、分離します。
そうすると、以下の問題を解くことになります。
長さ \(N\) の数列 \(A\) がある。\(f(x)=\sum_{i \in A} \max(0,i-x)+\max(0,x-(i+a))\) の最小値を求めよ。
これは、Slope Trickというデータ構造(テクニック?)を使用して高速に解くことが可能です。
投稿日時:
最終更新: