No.1467 Selling Cars
タグ : / 解いたユーザー数 19
作問者 :
QCFium
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もしくは右上の雲マークをクリックしてアカウントを作成してください。