No.1251 絶対に間違ってはいけない最小化問題
レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限
: 512 MB / スペシャルジャッジ問題 （複数の解が存在する可能性があります）
タグ : / 解いたユーザー数 187
作問者 :
Kazun
/ テスター :
Kanten4205
タグ : / 解いたユーザー数 187
作問者 :
Kazun
/ テスター :
Kanten4205
問題文最終更新日: 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もしくは右上の雲マークをクリックしてアカウントを作成してください。