No.1467 Selling Cars
タグ : / 解いたユーザー数 18
作問者 :
Kanten4205
/ テスター :
QCFium
問題文
かんてん君は、新車の販売店で働いています。この店では、車の色を整数によって表します。
今日、$M$ 人の客から注文がありました。$i$ 人目 $(1 \leq i \leq M)$ の客は、色 $A_i$ の車を注文しました。
店には $N$ 種類の色の車の在庫があり、各 $i(1 \leq i \leq N)$ について色 $B_i$ の車がちょうど $k$ 台だけあります。
かんてん君は、それぞれの客に、在庫の中からちょうど1台だけ選んで売ります。但し、一度売った車は、もう売ることができません。
客は、自分の希望の色と買った車の色の差が小さければ小さいほど喜びます。全ての客になるべく喜んでほしいかんてん君は、なるべく色の差の合計が小さくなるように、それぞれの客に買ってもらう車を選びます。
つまり、各 $i(1 \leq i \leq M)$ について $i$ 人目の客に色 $c_i$ の車を売ることにしたとき、$\displaystyle \sum_{i = 1}^M |A_i - c_i|$ を最小化したいです。
$k = 1, 2, \cdots, M$ のそれぞれにおいて $\displaystyle \sum_{i = 1}^M |A_i - c_i|$ の最小値を求めてください。
入力
$M\ N$
$A_1\ A_2\ ...\ A_M$
$B_1\ B_2\ ...\ B_N$
すべてのテストケースは、以下の制約を満たします：
- $1 \leq M \leq N \leq 2000$
- $1 \leq A_i \leq 10^9(1 \leq i \leq M)$
- $1 \leq B_i \leq 10^9(1 \leq i \leq N)$
- $i \neq j$のとき、$A_i \neq A_j, B_i \neq B_j$
- 入力は全て整数
出力
$M$ 行で出力してください。
$j(1 \leq j \leq M)$ 行目には、$k=j$ のときの $\displaystyle \sum_{i=1}^{M} |A_i - c_i|$ の最小値を出力してください。
サンプル
サンプル1
入力
3 3
1 2 3
2 9 6
出力
11
4
2
$k=1$ のとき、客 $1$ に $1$ 種類目の車、客 $2$ に $3$ 種類目の車、客 $3$ に $2$ 種類目の車をそれぞれ売ることで、 $\displaystyle \sum_{i=1}^{M} |A_i - c_i| = |1 - 2| + |2 - 6| + |3 - 9| = 1 + 4 + 6 = 11$ となります。
求める値をこれより小さくすることはできないので、この時の最小値は $11$ です。
$k=2$ のとき、客 $1$ に $1$ 種類目の車、客 $2$ に $1$ 種類目の車、客 $3$ に $3$ 種類目の車をそれぞれ売ることで、 $\displaystyle \sum_{i=1}^{M} |A_i - c_i| = |1 - 2| + |2 - 2| + |3 - 6| = 1 + 0 + 3 = 4$ となります。
求める値をこれより小さくすることはできないので、この時の最小値は $4$ です。
$k=3$ のとき、全ての客に $1$ 種類目の車をそれぞれ売ることで、 $\displaystyle \sum_{i=1}^{M} |A_i - c_i| = |1 - 2| + |2 - 2| + |3 - 2| = 1 + 0 + 1 = 2$ となります。
求める値をこれより小さくすることはできないので、この時の最小値は $2$ です。
サンプル2
入力
3 14
15 92 6
5 35 8 9 79 3 23 84 6 26 43 38 32 7
出力
14
14
14
$k$ の値によって、最小値が変わらない場合もあります。
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。