No.3527 Minimum Abs Sum
レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限
: 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 28
作問者 :
yu23578
/ テスター :
Yoyoyo8128
aa36
Germanium32
GaLLium
タグ : / 解いたユーザー数 28
作問者 :
yu23578
/ テスター :
Yoyoyo8128
aa36
Germanium32
GaLLium
問題文最終更新日: 2026-05-04 21:14:00
問題文
長さ $N$ の整数列 $A,B$ が与えられます。有理数 $x$ に対して、関数 $f(x)$ を以下のように定義します。
$$f(x) = \sum_{i=1}^N |A_i x - B_i|$$
$f(x)$ が最小値を取る $x$ のうち、最も小さい $x$ を $\mathrm{mod} 10^9+7$ で出力してください。
ただし、そのような $x$ が存在し、 $\mathrm{mod} 10^9+7$ で一意に表現できることが保証されています。
$x$ が有理数の時、 $x\ \mathrm{mod} 10^9+7$ とは
この問題において、答えの $x$ を既約分数 $\frac{P}{Q}$ で表した時、 $Q \not\equiv 0 (\mathrm{mod} 10^9+7)$ であることが保証されるので、$R \times Q \equiv P (\mathrm{mod} 10^9+7), 0 \le R < 10^9+7$ を満たす $R$ が一意に定まります。この $R$ を解答してください。
制約
- $1 \le N \le 2 \times 10^5$
- $|A_i|,|B_i| \le 10^9$
- $A_i \neq 0$ なる $i (1 \le i \le N)$ が存在する
- 答えの $x$ を既約分数で表したとき、分母は $10^9+7$ の倍数でない
- 入力はすべて整数
入力
$N$ $A_1\ A_2\ A_3\ \cdots\ A_N$ $B_1\ B_2\ B_3\ \cdots\ B_N$
出力
条件を満たす $x$ の最小値を $\mathrm{mod} 10^9+7$ で解答してください。最後に改行してください。
サンプル
サンプル1
入力
3 1 1 1 1 1 -1
出力
1
$f(x) = |x-1| + |x-1| + |x+1|$ です。 $x = 1$ のとき最小値 $f(1) = 1$ を取るので、 $1$ を出力してください。
サンプル2
入力
4 0 0 0 6 0 4 2 7
出力
166666669
サンプル3
入力
4 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000
出力
1
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。