No.3527 Minimum Abs Sum
タグ : / 解いたユーザー数 37
作問者 :
yu23578
/ テスター :
Yoyoyo8128
aa36
Germanium32
GaLLium
Problem Statement
You are given integer sequences $A,B$ of length $N$. For a rational number $x$, define the function $f(x)$ as follows.
$$f(x) = \sum_{i=1}^N |A_i x - B_i|$$
Among the values of $x$ at which $f(x)$ attains its minimum, output the smallest $x$ modulo $\mathrm{mod} 10^9+7$.
It is guaranteed that such an $x$ exists and can be uniquely represented in $\mathrm{mod} 10^9+7$.
What $x\ \mathrm{mod} 10^9+7$ means when $x$ is a rational number
In this problem, when the answer $x$ is expressed as an irreducible fraction $\frac{P}{Q}$, it is guaranteed that $Q \not\equiv 0 (\mathrm{mod} 10^9+7)$, sothe $R$ satisfying $R \times Q \equiv P (\mathrm{mod} 10^9+7), 0 \le R < 10^9+7$ is uniquely determined. Answer this $R$.
Constraints
- $1 \le N \le 2 \times 10^5$
- $|A_i|,|B_i| \le 10^9$
- There exists an $i (1 \le i \le N)$ such that $A_i \neq 0$
- When the answer $x$ is expressed as an irreducible fraction, its denominator is not a multiple of $10^9+7$
- All input values are integers
Input
$N$ $A_1\ A_2\ A_3\ \cdots\ A_N$ $B_1\ B_2\ B_3\ \cdots\ B_N$
Output
Output the minimum $x$ satisfying the condition, in $\mathrm{mod} 10^9+7$. Print a newline at the end.
Sample
Sample 1
Input
3 1 1 1 1 1 -1
Output
1
We have $f(x) = |x-1| + |x-1| + |x+1|$. The minimum value $f(1) = 2$ is attained at $x = 1$, so output $1$.
Sample 2
Input
4 0 0 0 6 0 4 2 7
Output
166666669
Sample 3
Input
4 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000
Output
1
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。