No.596 Mail Delivery
Problem Statement
Houses and mailboxes are lined up on a number line.Pieces of mail, each labeled with its destination house, have been posted in the mailboxes.
All pieces of mail must be collected from the mailboxes and delivered to their destination houses.
Find the minimum required travel distance.
The start and end points of the delivery may be chosen freely.
Also, any number of pieces of mail can be carried at once.
Input
$N$ $M$
$x_1$ $d_1$
$y_1$ $y_2$ $y_3$ ⋯⋯ $y_{d_1}$
$x_2$ $d_2$
$y_1$ $y_2$ $y_3$ ⋯⋯ $y_{d_2}$
$\vdots$
$x_M$ $d_M$
$y_1$ $y_2$ $y_3$ ⋯⋯ $y_{d_M}$
$1 \leq N \leq 7×10^6$
$1 \leq M \leq 5×10^5$
$0 \leq x_i < N$
$0 \leq y_i < N$
$1 \leq d_i ∧ \sum{d_i} \leq 10^6$
Houses and mailboxes are located at integer coordinates in [$0$,$N$). $M$ is the number of mailboxes.
$x_i$ is the position of the $i$-th mailbox.
$d_i$ is the number of pieces of mail in the $i$-th mailbox.
$y_j$ on the line following $x_i$ $d_i$ is the position of the destination house of the $j$-th letter in the $i$-th mailbox.
Note that the coordinates of a piece of mail's destination and of the mailbox it was posted in may be the same.
Output
Find the minimum travel distance required to deliver all pieces of mail to their destinations.
Sample
Sample 1
Input
6 1 0 1 1
Output
1
Sample 2
Input
9 4 0 3 2 7 6 6 2 8 5 1 4 2 7 0 1 4 2 1 6
Output
14
Sample 3
Input
10 5 5 1 1 9 2 0 4 6 3 8 7 2 1 4 2 7 0 1 4 2 1 6
Output
17
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。
37zigen
はむこ