問題一覧 > 通常問題

No.1251 絶対に間違ってはいけない最小化問題

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / スペシャルジャッジ問題 (複数の解が存在する可能性があります)
タグ : / 解いたユーザー数 131
作問者 : KazunKazun / テスター : Kanten4205Kanten4205
5 ProblemId : 4709 / 出題時の順位表
問題文最終更新日: 2020-10-08 03:18:09

問題文

整数 $A_1,\dots,A_N$ と正の整数 $B_1,\dots,B_N$ を用いて,実数を定義域とする関数 $f$ を
$\quad \displaystyle f(X)=\sum_{i=1}^N B_i |X-A_i|$
とする.このとき, $f$ を最小にする実数 $X$ とそのときの$f(X)$を求めよ.

ただし,実数を定義域とする関数 $g$ を最小にする実数 $Y$ とは,任意の実数 $Z$ に対して, $g(Y) \leq g(Z)$ を満たすことである. この問題の制約下で, $f$ を最小にする実数は少なくとも1つは存在することが示せる. なお, $f$ を最小にする実数が2つ以上存在する場合も考えられるが,その場合はそのうちの1つを出力すれば良い.

また,この問題において制約下では最小値が整数であることが示される.

注意

タイトルに "絶対に間違ってはいけない" とあるが, 実際には間違った解答を提出してもペナルティーはない.

制約

  • $1 \leq N \leq 2 \times 10^5$
  • $-10^6 \leq A_i \leq 10^6$
  • $1 \leq B_i \leq 10^6$
  • 入力は全て整数である.

入力

入力は以下の形式で標準入力から与えられる.
$N$
$A_1~A_2~\dots~A_N$
$B_1~B_2~\dots~B_N$

出力

$f$ を最小にする $X$ とその時の $f(X)$ を出力せよ.なお,この2つの数字は空白区切りとし,最後に改行すること.

サンプル

サンプル1
入力
1
0
1
出力
0 0

$f(X):=|X|$ を最小にする整数 $X$ は $X=0$ で,このとき, $f(0)=0$ である.

サンプル2
入力
3
1 2 3
1 2 3
出力
2 4

$X=2$ のとき, $f(2)=4$ で最小だが, $X=3$ としても $f(3)=4$ となる.

サンプル3
入力
10
1 1 2 3 5 8 13 21 34 55
1 2 3 4 5 1 2 3 4 5
出力
7.5 462

$f$ を最小にする $X$ は整数でなくてもよい.

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。