問題一覧 > 通常問題

No.1467 Selling Cars

レベル : / AI推定難易度 : 2800 / 実行時間制限 : 1ケース 4.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 19
作問者 : Kanten4205 / テスター : QCFium
お気に入りにしたユーザー ProblemId : 5061 / 自分の提出
問題文最終更新日: 2021-03-29 16:46:42
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 289 (Kanten4205’s Birthday Contest) (順位表) の他の問題:

Problem Statement

Kanten-kun works at a new car dealership. At this dealership, car colors are represented by integers.
Today, orders came in from $M$ customers. The $i$-th customer $(1 \leq i \leq M)$ ordered a car of color $A_i$.
The dealership has cars of $N$ different colors in stock, and for each $i(1 \leq i \leq N)$, there are exactly $k$ cars of color $B_i$.
Kanten-kun sells each customer exactly 1 car chosen from the stock. However, a car that has been sold once cannot be sold again.
A customer is happier the smaller the difference between the color they wanted and the color of the car they bought. Since Kanten-kun wants all customers to be as happy as possible, he chooses the car for each customer so that the total of the color differences is as small as possible.
That is, if he decides to sell a car of color $c_i$ to the $i$-th customer for each $i(1 \leq i \leq M)$, he wants to minimize $\displaystyle \sum_{i = 1}^M |A_i - c_i|$.
For each of $k = 1, 2, \cdots, M$, find the minimum value of $\displaystyle \sum_{i = 1}^M |A_i - c_i|$.

Input

$M\ N$
$A_1\ A_2\ ...\ A_M$
$B_1\ B_2\ ...\ B_N$

All test cases satisfy the following constraints:

  • $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)$
  • If $i \neq j$, then $A_i \neq A_j, B_i \neq B_j$
  • All input values are integers

Output

Print $M$ lines.
On line $j(1 \leq j \leq M)$, print the minimum value of $\displaystyle \sum_{i=1}^{M} |A_i - c_i|$ when $k=j$.

Sample

Sample 1
Input
3 3
1 2 3
2 9 6
Output
11
4
2

 When $k=1$, by selling customer $1$ a car of the type number $1$, customer $2$ a car of the type number $3$, and customer $3$ a car of the type number $2$, we get $\displaystyle \sum_{i=1}^{M} |A_i - c_i| = |1 - 2| + |2 - 6| + |3 - 9| = 1 + 4 + 6 = 11$. The value cannot be made smaller than this, so the minimum value in this case is $11$.
 When $k=2$, by selling customer $1$ a car of the type number $1$, customer $2$ a car of the type number $1$, and customer $3$ a car of the type number $3$, we get $\displaystyle \sum_{i=1}^{M} |A_i - c_i| = |1 - 2| + |2 - 2| + |3 - 6| = 1 + 0 + 3 = 4$. The value cannot be made smaller than this, so the minimum value in this case is $4$.
 When $k=3$, by selling every customer a car of the type number $1$, we get $\displaystyle \sum_{i=1}^{M} |A_i - c_i| = |1 - 2| + |2 - 2| + |3 - 2| = 1 + 0 + 1 = 2$. The value cannot be made smaller than this, so the minimum value in this case is $2$.

Sample 2
Input
3 14
15 92 6
5 35 8 9 79 3 23 84 6 26 43 38 32 7
Output
14
14
14

The minimum value may not change depending on the value of $k$.

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