Entries

スポンサーサイト (この記事を編集する[管理者用])

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

コメント

コメントの投稿

コメントの投稿
管理者にだけ表示を許可する

トラックバック

トラックバック URL
http://rsujskf.blog32.fc2.com/tb.php/2228-d6216ecf
この記事にトラックバックする(FC2ブログユーザー)

SPOJ 9510 - Ads Proposal [ADSPROP] (この記事を編集する[管理者用])

Source

Fudan University Local Contest #3
SPOJ 9510 [ADSPROP]

問題概要

N人 (100000以下) の人と,M個 (500000以下) の広告がある.
各広告は,N人のうちの誰かが広告主である.
各広告の,クリックされた回数と,長さが与えられる.クリックされた回数は全て異なる.それぞれ10^9以下.
Q個 (100000以下) のクエリが与えられるのでそれに答える問題.
各クエリでは,整数K (1以上10^9以下) が与えられるので,各広告主の最もクリックされた順番でK番目までの広告の長さの和を求める問題.
(広告主ごとに求めるのではなく,全ての広告主の広告の長さの和を求める.K個も広告を持っていない人に対してはすべての広告の長さの和)

解法

最初に,広告主ごとに,クリック回数で広告をソートしておくO(N + M log M).
そして,A[k]に各広告主のk番目の広告の長さの和を持っておき(O(M)),sum[k]でA[1]~A[k]の和をで計算しておく(O(M)).
後は,全てのクエリに対してO(1)で答えることができる.

コメント

コメントの投稿

コメントの投稿
管理者にだけ表示を許可する

トラックバック

トラックバック URL
http://rsujskf.blog32.fc2.com/tb.php/2228-d6216ecf
この記事にトラックバックする(FC2ブログユーザー)

Appendix

Recent Articles

ブログ内検索

Ads


(プライバシーポリシー)
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。