HOJ 1279 - Sequence Sum
問題概要
長さ$ \ N \ $の数列$ \ A \ (a_1,a_2,\ldots,a_N) \ $が与えられる。
次の条件を満たす数列$ \ B \ (b_1,b_2,\ldots,b_N) \ $を求めよ。
- 数列$ \ B \ $の$ \ i \ (1 \leq i \leq N) \ $番目の要素$ \ b_i \ $は数列$ \ A \ $の中で$ \ a_i \ $よりも値の大きい要素の総和である。
制約
- $1 \leq N \leq 10^5$
- $0 \leq a_i \leq 10^9$
解説
各$ \ b_i \ $を愚直に求めようとした場合計算量は$ \ O(N^2) \ $となりTLEです。 より高速に$ \ b_i \ $を求める必要があります。
解法はいくつか存在しますが、累積和と二分探索を用いることで高速に答えを求めることができます。
$A \ $を降順に並べ替えたものを$ \ A' \ $とすると、 $A'_k \gt A_i \ $を満たす最大の$ \ k \ $について、$A'_1 \ $から$ \ A'_k \ $までの総和が$ \ b_i \ $となります。 このような$ \ k \ $は二分探索により$ \ O(\log N) \ $で求めることができ、$A'_1 \ $から$ \ A'_k \ $までの総和は累積和で高速に求められます。
よってこの問題は計算量$ \ O(N \log N) \ $で解くことができます。
