競プロ精進記録
最近ようやく300点問題がまあまあ解けるようになってきたので、茶diffの400点問題を探しています。
今日解いたのはこれです!!
考えたこと
計算量はO(NlogN)まで間にあう。
愚直にやってたら O(N × Q ) となるので間に合わない…
Aをソートして、A_1 <= A_2 <= ・・・<=A_ｎとして、X_i <= A_kを満たす最小のｋを見つけたら、求める数は
X_i × (k - 1) - (A_1 + ・・・+ A_(k-1))
+ (A_k + ・・・+A_n) - X_i × ( n - ( k - 1))
を計算することで得られる (二行になっちゃってごめんなさい）
ここで、(A_1 + ・・・+ A_(k-1)) とかの部分は累積和でO(1)で計算できる。
Aはソートしてるから単調増加なので、二分探索でｋを探せば O(logN)で見つかる。
よって全体の計算量は、最初にAをソートしているので O(NlogN + QlogN) になり、間に合いそう!!
実装
二分探索をよく理解していないため、雑なコードになりました。
以下がコードです。
まとめ
通ったならなんでもいいですね。発想が前解いたやつと同じでした。
この記事が気に入ったらサポートをしてみませんか？