[ICPC2020 Shanghai R] Rice Arrangement
题意翻译
Wowo 是一名好客的新疆大叔。$k$ 名客人将在 Wowo 的房子里,围在圆桌旁享用新疆抓饭。$n(n \ge k)$ 把椅子已经被均匀的放置在桌子周围,每个客人坐在一把椅子上,没有两名客人坐在同一把椅子上。$k$ 份新疆抓饭已经放在了桌子上,每份抓饭都放在了一把椅子面前(可能没有客人坐在这把椅子上),没有两份抓饭放在同一个位置上。
作为服务员,你需要为每一名客人指定正好一碗抓饭。桌子可以旋转,每次你可以顺时针或逆时针旋转桌子 $\dfrac{2\pi}{n}$ 度。碗随着桌子旋转,但客人和椅子不会随之移动。当一碗饭转到某个客人面前时,他可以选择拿走这碗饭,或等待另一碗。
你想要最小化旋转桌子的次数,使得每个人可以最快得到饭。
题目描述
Wowo is a hospitable Xinjiang uncle. $k$ guests will have Uyghur Polo (a traditional Uyghur food) in Wowo's house around a big round table. $n$ ($n\ge k$) chairs are placed around the table uniformly. Each guest sits on a chair and no two guests sit on the same chair. $k$ bowls of Uyghur Polo are on the table. Each bowl is next to some chair ($\textbf{with or without}$ some guest sitting on it). No two bowls locate at the same position.
![](https://cdn.luogu.com.cn/upload/image_hosting/q3gqhsvq.png)
As a waiter, you are supposed to assign each person with exactly one bowl of Uyghur Polo. The table can be rotated, so each time you can turn it $\frac{2\pi}{n}$ degrees clockwise or counterclockwise. The bowls turn with the table while the chairs and guests do not move. When one bowl of Uyghur Polo is in front of a guest, he can either take it or wait for another.
You want to minimize the total times of table rotating so that everybody can have meals as quickly as possible.
(Formal definition: The boundary of the table is a circle. $n$ chairs are at $n$ points on the circle whose convex hull is a regular polygon with $n$ vertices. We name the points $0,\ldots, n-1$ in counterclockwise order. The $i$-th bowl is at point $b_i$ ($0\le b_i<n$) initially. The $i$-th guest is at point $a_i$ ($0\le a_i < n$) initially. If you turn the table counterclockwise, the bowl at point $b_i$ ($1\le i\le k$) will be moved to point $(b_i+ 1) \bmod n$ after the rotation. If you turn the table clockwise, the bowl at point $b_i$ ($1\le i\le k$) will be moved to point $(b_i-1) \bmod n$ after the rotation. ($x\bmod n$ is defined as the smallest nonnegative integer $r$ such that $x-r$ is a multiple of $n$.))
输入输出格式
输入格式
There are multiple test cases. The first line of the input contains an integer $T$, indicating the number of test cases. For each test case:
The first line contains two integers $n,k$ ($1\le n \le 10^9,1 \le k \le \min(n,1000)$) indicating the size of the table and the number of persons and bowls of Uyghur Polo.
In the second line, there are $k$ integers $a_1,a_2,\dots,a_k$ ($0 \le a_i < n$), indicating the positions of the persons. No two guests share the same position.
In the third line, there are $k$ integers $b_1,b_2,\dots,b_k$ ($0 \le b_i < n$), indicating the initial positions of the bowls. No two bowls of Uyghur Polo locate at the same position.
It is guaranteed that the sum of $k$ over all test cases does not exceed $5000$.
输出格式
For each test case, output the minimal total times of rotations such that each guest can have exactly one bowl of Uyghur Polo.
输入输出样例
输入样例 #1
1
4 2
0 3
1 2
输出样例 #1
2
输入样例 #2
1
14 5
0 12 13 8 9
9 2 6 13 5
输出样例 #2
6