Entries

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

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

コメント

コメントの投稿

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

トラックバック

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

UVa 12028 - A Gift from the Setter (この記事を編集する[管理者用])

Source

Modified National Programming Contest of Bangladesh (2011-06-19)
UVa 12028

問題概要

要素数n (10^5以下) の整数列が与えられる.
各要素の差の和
 Σ[i<j] |a[i]-a[j]|
を求める問題.
答えはlong longに収まる.

解法

まず,ソートして,途中までの和を全部求めておく. 後は,各要素a[i]ごとに,その要素より小さい要素との差の和はO(1)で計算できる.

コメント

コメントの投稿

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

トラックバック

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

Appendix

Recent Articles

ブログ内検索

Ads


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