SPOJ 12151 - Pizzamania [OPCPIZZA]

Source

12151 [OPCPIZZA]

問題概要

$N$ 人の人がいて,人 $k$ の所持金 $C_k$ が与えられる.
また,ピザの値段 $M$ が与えられる.
$2$ 人の所持金の和がピザの値段とピッタリ一致する場合のみ,その $2$ 人でピザを買って分け合えることができる.
ピザを分け合うことができる人のペアの数を求める問題.
ただし,所持金,ピザの値段は負になることもある.
つまり,$C_i + C_j = M$ となる $(i,j)$ はいくつ存在するかを求める問題.

解法

最初から所持金 $C_k$ をなぞっていって,$M-C_k$ の所持金を持つ人が今までに存在していれば答えに $1$ を足していく.
今までのなぞった人の所持金はハッシュなどに入れておけば時間計算量 $O(N)$ で求めることができる.
または,ソートしてから尺取法で求めるなど.

C言語によるスパゲッティなソースコード

この部分を表示するには表示権限を持つユーザーでログインする必要があります.


Current time: 2017年11月21日04時11分44秒
Last modified: 2014年06月12日19時41分37秒 (by laycrs)
Tags: Competitive_Programming Sphere_Online_Judge SPOJ_Classical
トップページに戻る

Logged in as: unknown user (not login)

ログイン: